AT_abc411_d [ABC411D] Conflict 2

$ 1 $ 台のサーバーと $ N $ 台の PC があります。 サーバーおよび各 PC はそれぞれ $ 1 $ つずつ文字列を保持しており、最初は全て空文字列です。 $ Q $ 個のクエリが与えられます。各クエリは以下のいずれかの形式です。 - `1 p`：PC $ p $ の文字列をサーバーの文字列で置き換える。 - `2 p s`：PC $ p $ の文字列の末尾に文字列 $ s $ を追加する。 - `3 p`：サーバーの文字列をPC $ p $ の文字列で置き換える。 全てのクエリを与えられた順に処理したときの最終的なサーバーの文字列を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ ここで $ \mathrm{query}_i $ は $ i $ 番目のクエリを表し、以下のいずれかの形式で与えられる。 ``` 1 p ``` ``` 2 p s ``` ``` 3 p ```

答えを出力せよ。

### Sample Explanation 1 - 最初、サーバーおよび PC $ 1,2 $ の文字列は全て空である。 - $ 1 $ 番目のクエリ： PC $ 1 $ の文字列の末尾に `at` を追加する。このとき、サーバー、PC $ 1,2 $ の文字列はそれぞれ空、`at`、空である。 - $ 2 $ 番目のクエリ： サーバーの文字列を PC $ 1 $ の文字列で置き換える。このとき、サーバー、PC $ 1,2 $ の文字列はそれぞれ `at`、`at`、空である。 - $ 3 $ 番目のクエリ： PC $ 2 $ の文字列の末尾に `on` を追加する。このとき、サーバー、PC $ 1,2 $ の文字列はそれぞれ `at`、`at`、`on` である。 - $ 4 $ 番目のクエリ： PC $ 2 $ の文字列をサーバーの文字列で置き換える。このとき、サーバー、PC $ 1,2 $ の文字列はそれぞれ `at`、`at`、`at` である。 - $ 5 $ 番目のクエリ： PC $ 2 $ の文字列の末尾に `coder` を追加する。このとき、サーバー、PC $ 1,2 $ の文字列はそれぞれ `at`、`at`、`atcoder` である。 - $ 6 $ 番目のクエリ： サーバーの文字列を PC $ 2 $ の文字列で置き換える。このとき、サーバー、PC $ 1,2 $ の文字列はそれぞれ `atcoder`、`at`、`atcoder` である。 よって、最終的なサーバーの文字列は `atcoder` です。 ### Sample Explanation 2 最終的なサーバーの文字列は空です。 ### Constraints - $ N,Q $ は整数 - $ 1\leq N,Q \leq 2\times 10^5 $ - 全てのクエリについて、 $ p $ は整数であり、 $ 1 \leq p\leq N $ - 全ての $ 2 $ 種類目のクエリについて、 $ s $ は英小文字からなる長さ $ 1 $ 以上の文字列 - 全ての $ 2 $ 種類目のクエリに対する $ s $ の長さの総和は $ 10^6 $ 以下