问题描述

有一个服务器和N台PC。服务器和每台PC各自持有一个字符串，初始时所有字符串都为空。

给出Q个查询，每个查询是以下三种格式之一：

1. 1 p：将PC p的字符串替换为服务器的字符串
2. 2 p s：将字符串s追加到PC p的字符串末尾
3. 3 p：将服务器的字符串替换为PC p的字符串

按照给定顺序处理所有查询后，找出服务器的最终字符串。

约束条件

• N, Q为整数
• 1 ≤ N, Q ≤ 2×10^5
• 对于每个查询，p是整数且1 ≤ p ≤ N
• 对于类型2的查询，s是长度至少为1的小写英文字母串
• 所有类型2查询的s长度总和不超过10^6

输入格式

输入从标准输入按以下格式给出：

N Q
query1
query2
...
queryQ

每个query是以下格式之一：

• 1 p
• 2 p s
• 3 p

输出格式

输出最终结果。

样例输入1

2 6
2 1 at
3 1
2 2 on
1 2
2 2 coder
3 2

样例输出1

atcoder

解释： 初始时服务器和PC1、PC2的字符串都为空。

1. 第1个查询：将"at"追加到PC1 → PC1="at"
2. 第2个查询：服务器=PC1 → 服务器="at"
3. 第3个查询：将"on"追加到PC2 → PC2="on"
4. 第4个查询：PC2=服务器 → PC2="at"
5. 第5个查询：将"coder"追加到PC2 → PC2="atcoder"
6. 第6个查询：服务器=PC2 → 服务器="atcoder"

样例输入2

100000 3
1 100
2 300 abc
3 200

样例输出2

(空字符串)

样例输入3

10 10
2 7 ladxf
2 7 zz
2 7 kfm
3 7
1 5
2 5 irur
3 5
1 6
2 6 ptilun
3 6

样例输出3

ladxfzzkfmirurptilun