题目描述

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

输入描述

第一行$2$个空格隔开的整数$n,q(1\le n,q\le 5\times10^4)$,表示宝石数量和操作次数。

第二行$3\times q$个空格隔开的整数$a_1,b_1,op_1,a_2,b_2,op_2...a_i,b_i,op_i(1\le a_i,b_i\le n,op_i\in {0,1})$,对第$i$次操作,表示将编号为$a_i$的宝石取下，放到编号为$b$的宝石旁边，当$op_i=0$时放到其前，否则放到其后。

保证$a_i\ne b_i$。

输出描述

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

样例

输入

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$。