AT_abc411_d [ABC411D] Conflict 2

There is one server and $ N $ PCs. The server and each PC each hold one string, and initially all strings are empty. $ Q $ queries are given. Each query is in one of the following formats: - `1 p`: Replace the string of PC $ p $ with the string of the server. - `2 p s`: Append string $ s $ to the end of the string of PC $ p $ . - `3 p`: Replace the string of the server with the string of PC $ p $ . Find the final string of the server after processing all queries in the given order.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Here, $ \mathrm{query}_i $ represents the $ i $ -th query and is given in one of the following formats: ``` 1 p ``` ``` 2 p s ``` ``` 3 p ```

Output the answer.

### Sample Explanation 1 - Initially, the strings of the server and PCs $ 1,2 $ are all empty. - $ 1 $ st query: Append `at` to the end of the string of PC $ 1 $ . At this time, the strings of the server, PC $ 1,2 $ are empty, `at`, empty, respectively. - $ 2 $ nd query: Replace the string of the server with the string of PC $ 1 $ . At this time, the strings of the server, PC $ 1,2 $ are `at`, `at`, empty, respectively. - $ 3 $ rd query: Append `on` to the end of the string of PC $ 2 $ . At this time, the strings of the server, PC $ 1,2 $ are `at`, `at`, `on`, respectively. - $ 4 $ th query: Replace the string of PC $ 2 $ with the string of the server. At this time, the strings of the server, PC $ 1,2 $ are `at`, `at`, `at`, respectively. - $ 5 $ th query: Append `coder` to the end of the string of PC $ 2 $ . At this time, the strings of the server, PC $ 1,2 $ are `at`, `at`, `atcoder`, respectively. - $ 6 $ th query: Replace the string of the server with the string of PC $ 2 $ . At this time, the strings of the server, PC $ 1,2 $ are `atcoder`, `at`, `atcoder`, respectively. Thus, the final string of the server is `atcoder`. ### Sample Explanation 2 The final string of the server is empty. ### Constraints - $ N,Q $ are integers - $ 1\leq N,Q \leq 2\times 10^5 $ - For every query, $ p $ is an integer and $ 1 \leq p\leq N $ . - For every query of type $ 2 $ , $ s $ is a string of length at least $ 1 $ consisting of lowercase English letters. - The sum of the lengths of $ s $ over all queries of type $ 2 $ is at most $ 10^6 $ .