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<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
#define MK make_pair
const ll E=1e18+7;
const ll MOD=1000000007;

template<typename T>
class weight_uft{
private:
    typedef pair<ull,T> parent_weight;
    vector<pair<parent_weight,ull>> uft; //{parent_weight,node}
    ull size;
    T err;
public:
    weight_uft(ull size,T err=(T)(1e9)):size(size),err(err){
        uft.resize(size);
        for(int i=0;i<size;i++){
            uft[i]={{i,(T)0},1};
        }
    }
    
    parent_weight search(ull where){
        if(uft[where].F.F==where){return uft[where].F;}
        parent_weight P=search(uft[where].F.F);
        uft[where].F.F=P.F;
        uft[where].F.S+=P.S;
        return uft[where].F;
    }
    
    bool same(ull a,ull b){
        if(search(a).F==search(b).F){return true;}
        return false;
    }
    
    T dist(ull from,ull to){
        if(!same(from,to)){return err;}
        return search(from).S-search(to).S;
    }
    
    bool add(ull from,ull to,T d){
        if(same(from,to) && dist(from,to)!=d){return false;}
        if(same(from,to)){return true;}
        parent_weight f=search(from);
        parent_weight t=search(to);
        if(uft[t.F].S>uft[f.F].S){
            uft[f.F].F.F=t.F;
            uft[f.F].F.S=d-f.S+t.S;
            uft[t.F].S=uft[t.F].S+uft[f.F].S;
        }
        else{
            uft[t.F].F.F=f.F;
            uft[t.F].F.S=f.S-t.S-d;
            uft[f.F].S=uft[f.F].S+uft[t.F].S;
        }
        return true;
    }
};



int main(){
    ll n,q;
    cin>>n>>q;
    weight_uft<ll> uft(n,E);
    while(q--){
        ll c;
        cin>>c;
        if(c){
            ll a,b;
            cin>>a>>b;
            if(!uft.same(a,b)){cout<<"?"<<endl;}
            else{cout<<uft.dist(a,b)<<endl;}
        }
        else{
            ll a,b,d;
            cin>>a>>b>>d;
            uft.add(a,b,d);
        }
    }
    
    
    return 0;
}