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 CPP):

Solution:
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
template<class A> struct UnionFind {
       vector<int> p;
       vector<int> rank;
       vector<A> diff_weight;
       UnionFind(int n = 1, A UNITY = 0) {
              init(n, UNITY);
       }
       void init(int n = 1, A UNITY = 0) {
              p.resize(n); rank.resize(n); diff_weight.resize(n);
              for (int i = 0; i < n; ++i) p[i] = i, rank[i] = 0, diff_weight[i] = UNITY;
       }
       int root(int x) {
              if (p[x] == x) {
                     return x;
              }
              else {
                     int r = root(p[x]);
                     diff_weight[x] += diff_weight[p[x]];
                     return p[x] = r;
              }
       }
       A weight(int x) {
              root(x);
              return diff_weight[x];
       }
       bool same(int x, int y) {
              return root(x) == root(y);
       }
       bool unite(int x, int y, A w) {
              w += weight(x); w -= weight(y);
              x = root(x); y = root(y);
              if (x == y) return false;
              if (rank[x] < rank[y]) swap(x, y), w = -w;
              if (rank[x] == rank[y]) ++rank[x];
              p[y] = x;
              diff_weight[y] = w;
              return true;
       }
       A diff(int x, int y) {
              return weight(y) - weight(x);
       }
};

int main() {
  int N, M;
  cin >> N >> M;
  UnionFind<int> uf(N);
  for (int i = 0; i < M; ++i) {
     int a, b, c, d;
     cin >> a;
     if (a == 0) {
      cin >> b >> c >> d;
       uf.unite(b, c, d);
     }
   else {
   cin >> b >> c;
   if (!uf.same(b, c)) cout << "?" << endl;
    else cout << uf.diff(b, c) << endl;
   }
  }
}