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:
class WeightedUnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        self.diff_weight = [0] * N
    
    def weight(self, v):
        self.find(v) # path compression
        return self.diff_weight[v]
    
    def dist(self, u, v):
        if self.is_connected(x, y):
            return self.weight(v) - self.weight(u)
        else:
            return None
    
    def find(self, v):
        if self.vertices[v] < 0:
            return v
        else:
            # path compression: reconnect v to the root
            root = self.find(self.vertices[v])
            self.diff_weight[v] += self.diff_weight[self.vertices[v]]
            self.vertices[v] = root
            return self.vertices[v]
    
    def union(self, u, v, w):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
            self.diff_weight[s2] = w - self.diff_weight[v] + self.diff_weight[u]
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            self.diff_weight[s1] = -w - self.diff_weight[u] + self.diff_weight[v]
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]
    
n, q = map(int, input().split())
wuf = WeightedUnionFind(n)
for _ in range(q):
    txt = input().split()
    if txt[0] == '0':
        x, y, z = map(int, txt[1:])
        wuf.union(x, y, z)
    else:
        x, y = map(int, txt[1:])
        res = wuf.dist(x, y)
        if res is not None:
            print(res)
        else:
            print('?')