排隊問題

題目敘述

一開始有$n$個人，編號為$1\sim n$，總共有$n$個隊伍，編號也是$1\sim n$。現在讓編號$1$的人排在編號$1$的隊伍、編號$2$的人排在編號$2$的隊伍...編號$n$的人排在編號$n$的隊伍。接著有$m$個指令，必須按先輸入後順序執行，指令有兩種，分別是0 a和，1 a b，兩種指令解說如下:

• 0 a b
  表示編號$a$的人從原來的位置離開，排到編號$b$的人的後面
• 1 a b
  表示編號$a$的隊伍的所有人，按原來順序排到編號$b$的隊伍的尾端，注意編號$a$的隊伍和編號$b$的隊伍都有可能沒人排隊

請你在所有操作都完成後，按順序輸出每一隊的人。

輸入說明

第一行有兩個整數$\;n,\;m$，$1 \leq n \leq 10^6,\;1 \leq m \leq 2*10^6$，接著有m行，每行有三個整數$\;t,\;a,\;b$，$t = 0 \; or \; 1,\; 1 \leq a \leq n,\;1 \leq b \leq n,\; a \neq b$。

輸出說明

按造順序輸出每一隊在所有操作都完成後的情況，行尾不能有空白，詳見範例輸入輸出。

範例輸入

6 4
0 4 3
0 6 5
1 2 5
1 6 5

範例輸出

#1: 1
#2:
#3: 3 4
#4:
#5: 5 6 2
#6:

配分方法

• 10% $n \leq 100$
• 20% $n \leq 1000$
• 30% $n \leq 10^4$
• 40% $n \leq 10^6$

Hints

備註

#1: 1
#2: 2
#3: 3
#4: 4
#5: 5
#6: 6

#1: 1
#2: 2
#3: 3 4
#4:
#5: 5
#6: 6

#1: 1
#2: 2
#3: 3 4
#4:
#5: 5 6
#6:

#1: 1
#2:
#3: 3 4
#4:
#5: 5 6 2
#6:

#1: 1
#2:
#3: 3 4
#4:
#5: 5 6 2
#6:

Judge Setting