AT_past202005_k コンテナの移動

有 $n$ 张桌子和 $n$ 个箱子。一个桌子上可以放多个箱子。最初，编号为 $i$ 的箱子被放在编号为 $i$ 的桌子上（$1 \le i \le n$）。 现在有 $q$ 次操作，每次操作给定三个参数 $f_i,t_i,x_i$，表示将编号 $x_i$ 的箱子及其上方的所有箱子从编号为 $f_i$ 的桌子搬运到编号为 $t_i$ 的桌子上的最上面的箱子的上方，而不改变它们的堆积顺序（见图。图中参数为：$f=1,t=2,x=4$）。 请按输入顺序执行这 $q$ 次操作，并在所有操作完成后，按顺序输出编号为 $i$ 的箱子所在的桌子编号。

第一行：两个整数 $n,q$。 从第二行开始数的 $q$ 行：每行三个整数 $f_i,t_i,x_i$。

$n$ 行，每行一个整数。第 $i$ 行应该输出 $i$ 号箱子最后所处的桌子的编号。 ### 数据规模 - 输入均为整数； - $2 \le n \le 2 \times 10^5$，$ 1\le q \le 2 \times 10^5$； - $1 \le f_i,t_i,x_i \le n$，$ f_i \neq t_i$，且每次操作前保证 $x_i$ 号箱子在编号为 $f_i$ 的桌子上。

### 注意 この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 与えられる入力は全て整数 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ f_i,\ t_i,\ x_i\leq\ N $ - $ f_i\ \neq\ t_i $ - コンテナ $ x_i $ はクエリを処理する時点で机 $ f_i $ 上にあることが保証される ### Sample Explanation 1 \- $ 1 $ 番目のクエリで机 $ 1 $ にあるコンテナ $ 1 $ を机 $ 2 $ に移します。このとき、机 $ 2 $ にはコンテナ $ 2 $ があるので、その上にコンテナ $ 1 $ を積み上げます。 - $ 2 $ 番目のクエリで机 $ 2 $ にあるコンテナ $ 2 $ とその上にあるコンテナ $ 1 $ を机 $ 3 $ に移します。このとき、机 $ 3 $ にはコンテナ $ 3 $ があるので、その上にコンテナ $ 2,1 $ を積み上げます。 - $ 3 $ 番目のクエリで机 $ 3 $ にあるコンテナ $ 3 $ とその上にあるコンテナ $ 2,1 $ を机 $ 1 $ に移します。 - $ 4 $ 番目のクエリで机 $ 1 $ にあるコンテナ $ 2 $ とその上にあるコンテナ $ 1 $ を机 $ 3 $ に移します。 - 最終的にコンテナ $ 1,2 $ は机 $ 3 $ に、コンテナ $ 3 $ は机 $ 1 $ にあります。