题目内容

小塔正在欣赏他的一串宝石项链。这个项链还没有封口，是一条链，初始时从左到右宝石分别编$1\ 2\ 3...n$。然而经过一段时间端详，小塔觉得他应该把某颗宝石取下，然后放到某颗宝石的前面或者后面去，小塔在正式进行调整前，想请你帮他模拟一下他的若干次调整，希望你能告诉他经过他若干次调整后宝石项链的样子。

输入描述

第一行$2$个空格隔开的整数n和q,表示宝石数量和操作次数。

第二行$3q$个空格隔开的整数$a_1b_1op_1a_2b_2op_2...a_qb_qop_q$,对第$i$次操作,表示将编号为$a_i$的宝石取下，放到编号为$b$的宝石旁边，当$op_i$,=$0$时放到其前，否则放到其后。

$1≤n,q≤50000$,$1≤a,b≤n$,$op_i∈{0,1}$。保证$a_i≠b_i$。

输出描述

输出一行$n$个整数，表示调整后,从左到右宝石的编号。

样例1

输入

5 3
1 2 1 3 2 0 5 4 0

输出

3 2 1 5 4

说明

初始$1\ 2\ 3\ 4\ 5$

第一次把$1$取下，放到$2$后，变成$2\ 1\ 3\ 4\ 5$

第二次把$3$取下，放到$2$前，变成$3\ 2\ 1\ 4\ 5$

第三次把$5$取下，放到$4$前，变成$3\ 2\ 1\ 5\ 4$。