← 返回题目列表

AtCoder · abc411_d

G. 冲突2

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

有一台服务器,并且 N 电脑。 服务器和每台PC各持有一个字符串,最初所有字符串都是空的。 给出了

Q 查询。每个查询均采用以下格式之一:

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

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

约束

  • N,Q 是整数
  • 1\leq N,Q \leq 2\times 10^5
  • 对于每个查询, p 是一个整数并且 1 \leq p\leq N.
  • 对于每个类型的查询 2, s 是长度至少为 1 由小写英文字母组成。
  • 的长度总和 s 类型的所有查询 2 最多是 10^6.

输入

输入由标准输入按以下格式给出:

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

在这里, \mathrm{query}_i 代表 i-th 查询,并以下列格式之一给出:

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
  • 最初,服务器和PC的字符串 1,2 全部为空。
  • 1st 查询:追加 at 到PC字符串的末尾 1。此时服务器、PC的字符串 1,2 为空, at,分别为空。
  • 2nd查询:将服务器的字符串替换为PC的字符串 1。此时服务器、PC的字符串 1,2 是 at, at,分别为空。
  • 3rd 查询:追加 on 到PC字符串的末尾 2。此时服务器、PC的字符串 1,2 是 at, at, on。
  • 4第查询:替换PC的字符串 2 与服务器的字符串。此时服务器、PC的字符串 1,2 是 at, at, at。
  • 5第查询:追加 coder 到PC字符串的末尾 2。此时服务器、PC的字符串 1,2 是 at, at, atcoder。
  • 6th 查询:将服务器的字符串替换为 PC 的字符串 2。此时服务器、PC的字符串 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