当前没有测试数据。

问题描述

有一台服务器和N台电脑。服务器和每台电脑各自持有一个字符串，最初所有字符串都是空的。

给定Q个查询。每个查询的格式如下：

1 p：将电脑p的字符串替换为服务器的字符串。

2 p s：将字符串s追加到电脑p的字符串末尾。

3 p：将服务器的字符串替换为电脑p的字符串。

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

约束条件

N,Q为整数

1≤N,Q≤2×10^5

对于每个查询，p是整数且1≤p≤N。

对于类型为2的每个查询，s是一个长度至少为1的字符串，由小写英文字母组成。

所有类型为2的查询中s的长度之和不超过10^6。

输入

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

N Q

query 1

query 2

⋮

query Q

这里，query i表示第i个查询，其格式如下：

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

最初，服务器和电脑1、2的字符串都是空的。

第1个查询：将字符串“at”追加到电脑1的字符串末尾。此时，服务器、电脑1、2的字符串分别为：空、at、空。

第2个查询：将服务器的字符串替换为电脑1的字符串。此时，服务器、电脑1、2的字符串分别为：at、at、空。

第3个查询：将字符串“on”追加到电脑2的字符串末尾。此时，服务器、电脑1、2的字符串分别为：at、at、on。

第4个查询：将电脑2的字符串替换为服务器的字符串。此时，服务器、电脑1、2的字符串分别为：at、at、at。

第5个查询：将字符串“coder”追加到电脑2的字符串末尾。此时，服务器、电脑1、2的字符串分别为：at、at、atcoder。

第6个查询：将服务器的字符串替换为电脑2的字符串。此时，服务器、电脑1、2的字符串分别为：atcoder、at、atcoder。

因此，服务器的最终字符串是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