D - Conflict 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

1 台のサーバーと N 台の PC があります。 サーバーおよび各 PC はそれぞれ 1 つずつ文字列を保持しており、最初は全て空文字列です。

Q 個のクエリが与えられます。各クエリは以下のいずれかの形式です。

  • 1 p：PC p の文字列をサーバーの文字列で置き換える。
  • 2 p s：PC p の文字列の末尾に文字列 s を追加する。
  • 3 p：サーバーの文字列をPC p の文字列で置き換える。

全てのクエリを与えられた順に処理したときの最終的なサーバーの文字列を求めてください。

制約

  • N,Q は整数
  • 1\leq N,Q \leq 2\times 10^5
  • 全てのクエリについて、p は整数であり、1 \leq p\leq N
  • 全ての 2 種類目のクエリについて、s は英小文字からなる長さ 1 以上の文字列
  • 全ての 2 種類目のクエリに対する s の長さの総和は 10^6 以下

入力

入力は以下の形式で標準入力から与えられる。

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

ここで \mathrm{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
  • 最初、サーバーおよび PC 1,2 の文字列は全て空である。
  • 1 番目のクエリ： PC 1 の文字列の末尾に at を追加する。このとき、サーバー、PC 1,2 の文字列はそれぞれ空、at、空である。
  • 2 番目のクエリ： サーバーの文字列を PC 1 の文字列で置き換える。このとき、サーバー、PC 1,2 の文字列はそれぞれ at、at、空である。
  • 3 番目のクエリ： PC 2 の文字列の末尾に on を追加する。このとき、サーバー、PC 1,2 の文字列はそれぞれ at、at、on である。
  • 4 番目のクエリ： PC 2 の文字列をサーバーの文字列で置き換える。このとき、サーバー、PC 1,2 の文字列はそれぞれ at、at、at である。
  • 5 番目のクエリ： PC 2 の文字列の末尾に coder を追加する。このとき、サーバー、PC 1,2 の文字列はそれぞれ at、at、atcoder である。
  • 6 番目のクエリ： サーバーの文字列を 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







Score : 425 points







Problem Statement
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.











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.
    • 
















Input
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
Output the answer.















Sample Input 1
2 6
2 1 at
3 1
2 2 on
1 2
2 2 coder
3 2












Sample Output 1
atcoder



    

  • Initially, the strings of the server and PCs 1,2 are all empty.
    • 

  • 1st 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.
    • 

  • 2nd 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.
    • 

  • 3rd 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.
    • 

  • 4th 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.
    • 

  • 5th 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.
    • 

  • 6th 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 Input 2
100000 3
1 100
2 300 abc
3 200












Sample Output 2


The final string of the server is empty.













Sample Input 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












Sample Output 3
ladxfzzkfmirurptilun