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 UnionFind:
  def __init__(self, n):
    self.tree = [-1] * n
    self.rank = [0] * n
    self.diff_weight = [0] * n
  
  def unite(self, a, b, w):
    w += self.weight(a)
    w -= self.weight(b)
    a = self.root(a)
    b = self.root(b)
    if a == b:
      return
    if self.rank[a] < self.rank[b]:
      a, b = b, a
      w *= -1
    if self.rank[a] == self.rank[b]:
      self.rank[a] += 1
    self.tree[b] = a
    self.diff_weight[b] = w
    
  def root(self, a):
    if(self.tree[a] < 0):
      return a
    else:
      res = self.root(self.tree[a])
      self.diff_weight[a] += self.diff_weight[self.tree[a]]
      self.tree[a] = res
      return self.tree[a]

  def same(self, a, b):
    return self.root(a) == self.root(b)

  def weight(self, a):
    self.root(a)
    return self.diff_weight[a]

  def diff(self, a, b):
    return self.weight(b) - self.weight(a)

import sys

stdin = sys.stdin
na = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())

def main():
  n, m = na()
  uf = UnionFind(n)
  for _ in range(m):
    t = list(na())
    a, b, c = t[0], t[1], t[2]
    if a == 0:
      d = t[3]
      uf.unite(b, c, d)
    else:
      if uf.same(b, c):
        print(uf.diff(b, c))
      else:
        print("?")

main()