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>

using namespace std;

struct edge {
  int dest;
  int weight; // = dest minus curr
};

class UF {
public:
  vector<edge> v;
  UF(int n) { v = vector<edge>(n, {-1, 0}); }

  void uf_union(int x, int y, int y_minus_x) {
    auto x_res = uf_find(x);
    auto y_res = uf_find(y);
    int loc_x = x_res.dest;
    int loc_y = y_res.dest;
    if (loc_x == loc_y)
      return;
    if (v[loc_x].dest <
        v[loc_y].dest) { // x's set has more elements -- join y to x
      v[loc_x].dest += v[loc_y].dest;
      v[loc_y] = {loc_x, x_res.weight - y_res.weight - y_minus_x};
    } else {
      v[loc_y].dest += v[loc_x].dest;
      v[loc_x] = {loc_y, y_res.weight - x_res.weight + y_minus_x};
    }
  }
  void uf_union(int x, int y) { uf_union(x, y, 0); }

  edge uf_find(int x) {
    if (v[x].dest < 0)
      return {x, 0};
    edge tmp = uf_find(v[x].dest);
    tmp.weight += v[x].weight;
    v[x] = tmp;
    return v[x];
  }
};

int main() {
  int n, q;
  cin >> n >> q;
  UF uf(n);
  int c, x, y;
  while (cin >> c >> x >> y) {
    if (c == 0) {
      int z;
      cin >> z;
      uf.uf_union(x, y, z);
    }
    if (c == 1) {
      edge x_res = uf.uf_find(x);
      edge y_res = uf.uf_find(y);
      if (x_res.dest != y_res.dest) {
        cout << "?" << endl;
      } else {
        cout << x_res.weight - y_res.weight << endl;
      }
    }
  }
}