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:
idx_com = 0
idx_x = 1
idx_y = 2
idx_z = 3

n, nq = map(int, input().split())
parents = list(range(n))
ranks = [0] * n
weights = [0] * n

def find(x):
    if parents[x] == x:
        return x
    y = find(parents[x])
    weights[x] += weights[parents[x]]
    parents[x] = y
    return y

def unite(x, y, w):
    root_x = find(x)
    root_y = find(y)

    if ranks[root_x] < ranks[root_y]:
        parents[root_x] = root_y
        weights[root_x] = -w - weights[x] + weights[y]
    else:
        parents[root_y] = root_x
        weights[root_y] = +w - weights[y] + weights[x]
        if ranks[root_x] == ranks[root_y]:
            ranks[root_x] += 1

def same(x, y):
    return find(x) == find(y)

def diff(x, y):
    return weights[y] - weights[x]

for _ in range(nq):
    q = list(map(int, input().split()))
    if q[idx_com] == 0:
        unite(q[idx_x], q[idx_y], q[idx_z])
    else:
        if same(q[idx_x], q[idx_y]):
            print(diff(q[idx_x], q[idx_y]))
        else:
            print("?")