Problem: There is a sequence $A = a_0, a_1, ..., a_{n-1}$. You are given the following information and questions.

* relate$(x, y, z)$: $a_y$ is greater than $a_x$ by $z$
* diff$(x, y)$: report the difference between $a_x$ and $a_y$ $(a_y - a_x)$

Constraints

* $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$
* There are no inconsistency in the given information

Input


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


In the first line, $n$ and $q$ are given. Then, $q$ information/questions are given in the following format.


0 $x \; y\; z$


or


1 $x \; y$


where '0' of the first digit denotes the relate information and '1' denotes the diff question.

Output

For each diff question, print the difference between $a_x$ and $a_y$ $(a_y - a_x)$.

Example

Input

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


Output

2
?
10

Solution (in PYTHON3):

Solution:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, Q = map(int, readline().split())
*p, = range(N)
data = [0]*N
def root(x):
    if x == p[x]:
        return x
    r = p[x]
    p[x] = y = root(r)
    data[x] += data[r]

    return y
def unite(x, y, z):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        data[py] = data[x] - data[y] - z
    else:
        p[px] = py
        data[px] = data[y] - data[x] + z
    return 1


ans = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        x, y = cmd
        px = root(x); py = root(y)
        if px == py:
            ans.append(str(data[x] - data[y]))
        else:
            ans.append("?")
    else:
        x, y, z = cmd
        unite(x, y, z)
write("\n".join(ans))
write("\n")