题目背景

每位同学都有自己唯一的正整数编号，体育活动前，一部分同学排好一条长队，还有一部分同学没有排队。最后在老师的指挥下，所有同学都排在了长队中。

题目描述

通过二元组的方式提供最初的长队中的排队情况，例如二元组 $\verb|(p,q)|$ 就表示长队中编号为 $\verb|p|$ 的同学的后面是编号为 $\verb|q|$ 的同学。特别地，如果 $\verb|q=0|$ 则意味着编号为 $\verb|p|$ 的同学后面没有同学（也就是编号为 $\verb|p|$ 的同学在队尾）。

老师的指挥可以看成一系列的三元组指令 $\verb|(f1,f2,pos)|$，就是将编号为 $\verb|f1|$ 的同学调整到编号为 $\verb|f2|$ 的同学的前面或者后面，例如指令 $\verb|(2,1,B)|$ 表示将编号为 $2$ 的同学调整到编号为 $1$ 的同学的前面，指令 $\verb|(5,6,A)|$ 表示将编号为 $5$ 的同学调整到编号为 $6$ 的同学的后面。老师发出三元组指令 $\verb|(f1,f2,pos)|$的时候，编号为 $\verb|f2|$ 的同学肯定在队列中，但是编号为 $\verb|f1|$ 的同学可能在队列中也可能还没有在队列中。

依次输出最终队列中所有同学的编号。

输入格式

第一行是两个正整数 $n,m$，分别表示提供最初的长队中的排队情况的二元组的数量和老师发出的指令三元组的数量；

接下来有 $n$ 行，每行是两个整数 $\verb|p,q|$，对应一个最初的长队中的排队情况的二元组；

再接下来有 $m$ 行，每行是两个整数 $\verb|f1,f2|$ 和一个字符 $\verb|pos|$，对应老师发出的一个指令三元组，字符 $\verb|pos|$ 取值是 A 或者 B；

输出格式

一行，若干用一个空格隔开的正整数，依次是最终队列中所有同学的编号。

输入输出样例

5 4
2 5
1 2
5 4
3 1
4 0
1 3 B
6 5 A
4 1 B
4 3 A

1 3 4 2 5 6

说明/提示

👀️ 对于输入样例，可知最初长队中同学的编号依次是 $\verb|3,1,2,5,4|$；

经过指令 $\verb|(1,3,B)|$ 调整后，长队中同学的编号依次是 $\verb|1,3,2,5,4|$；

经过指令 $\verb|(6,5,A)|$ 调整后，长队中同学的编号依次是 $\verb|1,3,2,5,6,4|$；

经过指令 $\verb|(4,1,B)|$ 调整后，长队中同学的编号依次是 $\verb|4,1,3,2,5,6|$；

经过指令 $\verb|(4,3,A)|$ 调整后，长队中同学的编号依次是 $\verb|1,3,4,2,5,6|$；

👀️ 对于 $100\%$ 的数据，参与排队的同学数量不超过 $50000$，$1 \leq n,m \leq 50000$，所有二元组保证最初的长队肯定存在，所有三元组保证对应的同学在队列中位置的调整有意义。