AT_abc395_d [ABC395D] Pigeon Swap

鳩 $ 1, $ 鳩 $ 2,\ldots, $ 鳩 $ N $ の $ N $ 羽の鳩と、巣 $ 1, $ 巣 $ 2,\ldots, $ 巣 $ N $ の $ N $ 個の巣があります。 はじめ、鳩 $ i $ $ (1\leq i\leq N) $ は巣 $ i $ にいます。 鳩たちに対して $ Q $ 回の操作を行います。 操作は次の $ 3 $ 種類のうちのいずれかです。 - 種類 $ 1 $ : 整数 $ a,b $ $ (1\leq a\leq N,1\leq b\leq N) $ が与えられる。鳩 $ a $ を今いる巣から取り出し、巣 $ b $ へ移動する。 - 種類 $ 2 $ : 整数 $ a,b $ $ (1\leq a\lt b\leq N) $ が与えられる。巣 $ a $ にいる鳩をすべて巣 $ b $ へ移動し、巣 $ b $ にいる鳩をすべて巣 $ a $ へ移動する。これら $ 2 $ つの移動は一斉に行われる。 - 種類 $ 3 $ : 整数 $ a $ $ (1\leq a\leq N) $ が与えられる。鳩 $ a $ が今いる巣の番号を報告する。 $ Q $ 回の操作を順に行ったときの、種類 $ 3 $ の各操作における報告の結果を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ op _ 1 $ $ op _ 2 $ $ \vdots $ $ op _ Q $ ただし、 $ i+1 $ 行目の入力 $ op _ i $ は $ i $ 番目の操作を表しており、 $ op _ i $ は次のいずれかの形式である。 $ i $ 番目の操作が種類 $ 1 $ の操作のとき、 $ i+1 $ 行目は次の形式で与えられる。 > $ 1 $ $ a $ $ b $ これは、与えられる整数を $ a $ と $ b $ として種類 $ 1 $ の操作を行うことを表している。 $ i $ 番目の操作が種類 $ 2 $ の操作のとき、 $ i+1 $ 行目は次の形式で与えられる。 > $ 2 $ $ a $ $ b $ これは、与えられる整数を $ a $ と $ b $ として種類 $ 2 $ の操作を行うことを表している。 $ i $ 番目の操作が種類 $ 3 $ の操作のとき、 $ i+1 $ 行目は次の形式で与えられる。 > $ 3 $ $ a $ これは、与えられる整数を $ a $ として種類 $ 3 $ の操作を行うことを表している。

与えられる種類 $ 3 $ の操作の個数を $ q $ 個として、 $ q $ 行にわたって出力せよ。 $ i $ 行目 $ (1\leq i\leq q) $ には、種類 $ 3 $ の操作のうち $ i $ 番目の操作で報告される巣の番号を出力せよ。

### Sample Explanation 1 与えられる操作で、鳩は以下の図のように移動します。  種類 $ 3 $ の操作でそれぞれ報告すべき巣の番号は $ 4,5,2,5 $ なので、`4` `5` `2` `5` を $ 4 $ 行にわたって出力してください。 ### Sample Explanation 2 種類 $ 1 $ の操作で、鳩を取り出した巣にそのまま戻す場合もあります。 ### Constraints - $ 1\leq N\leq10 ^ 6 $ - $ 1\leq Q\leq3\times10 ^ 5 $ - 入力される操作はすべて種類 $ 1, $ 種類 $ 2, $ 種類 $ 3 $ のいずれかである。 - 入力される操作は問題文中の制約を満たす。 - 入力される操作のうちに種類 $ 3 $ の操作が $ 1 $ つ以上含まれる。 - 入力はすべて整数