魂界

題目敘述

上次我們說過，宿主死亡後，惡魔並不會消失，而會等待時機進入下一個身體成為某人的慾望，在這之前他們都會待在那裡呢？這個世界為了能量守恆，因此宿主死亡後惡魔是不可以待在人間的，他們會進入一個被我們稱為魂界的亞空間中，他們會在其中增強自己的實力，不斷的訓練。實力較強的惡魔通常可以在魂界待比較久（所謂的實力就是能量值，我們上次說過了），他們會把實力較弱的惡魔趕去人間投胎，而實力較弱的惡魔為了能在魂界生存，所以常常組成一個團體，他們提升能量值的時候都是一起提升的，我們稱之為「成長」，順帶一提一隻惡魔也可以是一個團體。兩個團體可以融合成一個更大的團體我們，稱之為「融合」。因為低等惡魔組成的團體因為不斷融合和成長而越來越強大，讓現在的高等惡魔們有一點困擾，因此他們決定雇用你來分析每個新進來魂界的低等惡魔，身為卦長的弟子，相信你一定可以做到的。

輸入說明

第一行有兩個數字$N$和$Q$，$1 \leq N \leq 10^5,\; 1 \leq Q \leq 10^6$，表示有$N$隻新進來的低等惡魔，編號為$0 \sim N-1$（因為是新進魂界所以能量值都是0，而且還沒有開始融合），和$Q$個事件的發生，接著會有$Q$行。事件有三種，如下:

1. $0 \; x$
   高等惡魔向你詢問編號$x$的低等惡魔目前的實力是多少
2. $1 \; x \; p$
   你觀察到編號$x$的惡魔所在的團體成長了$p$單位的能量值，保證$p$在整數範圍
3. $2 \; a \; b$
   你觀察到編號$a$的惡魔所在的團體和編號$b$的惡魔所在的團體發生了合併

輸出說明

對於每個高等惡魔的詢問，請輸出編號$x$的低等惡魔的實力。若第三種事件發生且$a$和$b$早就已經在同一個團體中了，請輸出"SM"不含引號

範例輸入 1

10 32
1 1 5
1 2 6
1 3 7
1 4 9
0 1
0 2
0 3
0 4
2 2 1
2 3 4
0 1
0 2
0 3
0 4
1 1 10
1 2 20
1 3 30
1 4 40
0 1
0 2
0 3
0 4
2 1 3
1 1 1
1 2 2
1 3 3
1 4 4
0 1
0 2
0 3
0 4
2 3 4

範例輸出 1

5
6
7
9
5
6
7
9
35
36
77
79
45
46
87
89
SM

配分方法

• 0% 範例測資
• 40% $N \leq 1000, \; Q \leq 10000$
• 60% 題目範圍

Hints

備註

Judge Setting