重み付きUnion Find木

数列 $A = a_0, a_1, ... a_{n-1}$ に対して、以下の情報・質問が与えられます。

• relate$(x, y, z)$: $a_y$ は$a_x$より$z$大きい
• diff$(x, y)$: $a_x$ と$a_y$の差、$a_y-a_x$ を報告せよ

入力

$n \; q$
$query_1$
$query_2$
:
$query_q$

１行目に数列の要素数 $n$, 情報・質問の総数$q$ が与えられます。続く $q$ 行に各情報・質問が与えられます。各情報・質問は

0 $x \; y \; z$

または

1 $x \; y$

の形式で与えられ、最初の数字が'0'のとき relate、'1' のときdiffを表します。

出力

各 diff 質問について、$a_x$ と $a_y$ の差$(a_y - a_x)$を１行に出力してください。ただし、その時点で$a_x$と$a_y$の差が判断できない場合は'?'を出力してください。

制約

• $2 \leq n \leq 100,000$
• $1 \leq q \leq 200,000$
• $0 \leq x, y < n$
• $x \ne y$
• $0 \leq z \leq 10000$
• 矛盾するrelate情報は与えられない

入力例

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

出力例

2
?
10

---