#3325. 冲突

冲突

问题描述

有一个服务器和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