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:
/*
参考にしたもの

Tにできるものはアーベル群(足し算と引き算ができる代数系)
unitは単位元

Union-Find.cpp
https://qiita.com/drken/items/cce6fc5c579051e64fab
*/

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;

template<typename T>
struct WeightedUnionFind{
    T unit;
    vector<int> par;
    vector<int> es;
    vector<T> ws;
    WeightedUnionFind(int N,T unit) : par(N,-1),es(N,0),ws(N,unit),unit(unit) {}
    
    //初期化
    void init(int N){
        par.assign(N,-1);
        es.assign(N,0);
        ws.assign(N,unit);
    }
    //rootを探す
    int find(int x){
        if(par[x]<0) return x;
        else{
            int r=find(par[x]); //先に圧縮
            ws[x]+=ws[par[x]];
            return par[x]=r;
        } 
    }
    //集合の要素数
    int usize(int x) {return -par[find(x)];}
    //集合の辺の数
    int esize(int x) {return es[find(x)];}
    //xのrootを0にしたときの重さ 最初に圧縮する
    T weight(int x){find(x); return ws[x];}
    //y-x
    //これをやる前にsameで同じ集合にあるかを確認する
    T diff(int x,int y){return weight(y)-weight(x);}

    //weight(y)-weight(x)となるようにmergeする
    //xとyがすでに繋がっていたらfalseを返す weightはそのまま
    bool unite(int x,int y,T w){
        w+=weight(x); w-=weight(y);
        x=find(x);
        y=find(y);
        es[x]++;
        if(x==y) return false;

        if(usize(x)<usize(y)) swap(x,y),w=-w;
        par[x]+=par[y];
        es[x]+=es[y];
        par[y]=x;
        ws[y]=w;
        return true;
    }

    bool same(int x,int y) {return find(x)==find(y);}

};

signed main(void){
    int n,q;
    cin>>n>>q;
    WeightedUnionFind<ll> uf(n,0LL);
    while(q--){
        int a;
        cin>>a;
        if(a==0){
            int x,y,z;
            cin>>x>>y>>z;
            uf.unite(x,y,z);
        }else{
            int x,y;
            cin>>x>>y;
            if(uf.same(x,y)) cout<<uf.diff(x,y)<<endl;
            else cout<<"?"<<endl;
        }
    }
}