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:
#!/usr/bin/env python3
# DSL_1_B: Weighted Union Find Trees


class WeightedUnionFind:
    def __init__(self, n):
        self.n = n
        self.nodes = [i for i in range(n)]
        self.weights = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def connected(self, i, j):
        wi, ri = self.root(i)
        wj, rj = self.root(j)
        return ri == rj

    def union(self, i, j, w):
        wi, ri = self.root(i)
        wj, rj = self.root(j)
        if ri == rj:
            return

        if self.size[ri] < self.size[rj]:
            self.nodes[ri] = rj
            self.weights[ri] = wj - wi + w
            self.size[rj] += self.size[ri]
        else:
            self.nodes[rj] = ri
            self.weights[rj] = wi - wj - w
            self.size[ri] += self.size[rj]

    def weight(self, i, j):
        wi, ri = self.root(i)
        wj, rj = self.root(j)
        if ri != rj:
            raise ValueError('{} and {} is not connected'.format(i, j))

        return wi - wj

    def root(self, i):
        r = self.nodes[i]
        w = self.weights[i]
        while r != self.nodes[r]:
            w += self.weights[r]
            r = self.nodes[r]
        return w, r


def run():
    n, q = [int(i) for i in input().split()]
    wuf = WeightedUnionFind(n)

    for _ in range(q):
        com, *args = input().split()
        if com == '0':
            wuf.union(*[int(i) for i in args])
        elif com == '1':
            x, y = [int(i) for i in args]
            if wuf.connected(x, y):
                print(wuf.weight(x, y))
            else:
                print('?')


if __name__ == '__main__':
    run()