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;


vector<int> point;
vector<int> Rank;
vector<int> Cost;


void CreateSet(int x);
int Find(int x);
void Relate(int x, int y, int z);
void Diff(int x, int y);
int main() {
    int n,q;
    int operation;
    int x,y,z;
    cin >> n >> q;

    for (int i = 0; i < n; ++i) {
        CreateSet(i);
    }

    for (int j = 0; j < q; ++j) {
        cin >> operation >> x >> y;
        if(operation == 0){
            cin >> z;
            Relate(x,y,z);
        }else{
            Diff(x,y);
        }
    }
    return 0;
}
void CreateSet(int x){
    point.push_back(x);
    Rank.push_back(0);
    Cost.push_back(0);
}
int Find(int x){
    int prev = point[x];
    if (x != point[x])
    {
        point[x] = Find(point[x]);
    }
    Cost[x] += Cost[prev];
    return point[x];
}
void Relate(int x, int y, int z){
    int rootX = Find(x);
    int rootY = Find(y);
    if(rootX == rootY){
        // the same union
        return;
    }
    z = z + Cost[x] - Cost[y];

    if(Rank[rootY] > Rank[rootX]){
        point[rootX] = rootY;
        Cost[rootX] = -z;
        if(Rank[rootX] == Rank[rootY]){
            Rank[rootY] += 1;
        }
    }else{
        point[rootY] = rootX;
        Cost[rootY] = z;
    }
}
void Diff(int x, int y){
    if(Find(x) == Find(y)){
        cout << Cost[y] - Cost[x] << endl;
    }else{
        cout << "?" << endl;
    }
}