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
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

def diff(node_a, node_b):
    root_a, cost_a = node_a.root(0)
    root_b, cost_b = node_b.root(0)
    if root_a == root_b:
        return True, cost_a - cost_b
    else:
        return False, cost_a - cost_b

def merge(node_a, node_b, weight):
    root_a, cost_a = node_a.root(0)
    root_b, cost_b = node_b.root(0)
    root_a.weight = weight + cost_b - cost_a
    root_a.is_root = False
    root_a.parent = root_b

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.weight = 0
    
    def root(self, cost):
        if self.is_root:
            return self, cost
        root, max_ = self.parent.root(cost + self.weight)
        self.parent = root
        self.weight = max_ - cost
        return root, max_

def main():
    n, q = map(int, input().split())
    
    nodes = [Node() for i in range(n)]

    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            x, y, z = query[1:]
            if not diff(nodes[x], nodes[y])[0]:
                merge(nodes[x], nodes[y], z)
        else:
            x, y = query[1:]
            jud, ans = diff(nodes[x], nodes[y])
            if jud:
                print(ans)
            else:
                print("?")

if __name__ == "__main__":
    main()