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 <bits/stdc++.h>
#define LL              long long
#define SL(n)           scanf("%lld",&n)
#define LF              double
#define SF(n)           scanf("%lf",&n)

#define pb              push_back
#define ff              first
#define ss              second
#define mp              make_pair

#define ON(n,i)         (n|(1<<i))
#define OFF(n,i)        (n&(~(1<<i)))
#define CHK(n,i)        (n&(1<<i))

#define SET(arr)        memset( arr , -1 , sizeof arr)
#define RESET(arr)      memset( arr,0,sizeof arr)

#define srt(v)          sort(v.begin(),v.end())
#define uniq(v)			v.resize(distance(v.begin(),unique(v.begin(),v.end())))
#define found( s,d )    (s.find(d) != s.end())

#define FOR(i,s,e)      for( LL i = s ; i<=e ; i++ )

#define FILEIN          freopen("in.txt","r",stdin)
#define FILEOUT         freopen("out.txt","w",stdout)

using namespace std;

#define lim 100100

struct dsuNode{
    LL parent , Distance;
}Info[lim];

LL ParentOf( LL u ){
    if( Info[u].parent == u ) return u;
    LL p = ParentOf( Info[u].parent );
    Info[u].Distance += Info[ Info[u].parent ].Distance;
    return Info[u].parent = p;
}

bool Union( LL u, LL v, LL w ){

    ParentOf(u); ParentOf(v);
    w = w - Info[u].Distance + Info[v].Distance;
    u = ParentOf(u);
    v = ParentOf(v);
    if( u == v ) return true;
    Info[u].parent = ParentOf(v);
    Info[u].Distance = w;
    return false;

}

int main(){
    //FILEIN;
    LL n,m;
    SL(n); SL(m);
    FOR(i,1,n){
        Info[i].parent = i;
        Info[i].Distance = 0;
    }
    while(m--){
        LL t;
        SL(t);
        if(t==0){
            LL x,y,z;
            SL(x); SL(y); SL(z);
            x++,y++;
            Union(x,y,z);
        }
        else{
            LL x,y;
            SL(x); SL(y);
            x++,y++;
            //cout<<"DEBUG: "<<ParentOf(x)<<' '<<ParentOf(y)<<endl;
            if( ParentOf(x)!=ParentOf(y) ) printf("?\n");
            else{
                ParentOf(x); ParentOf(y);
                printf("%lld\n", ( Info[x].Distance - Info[y].Distance ));
            }
        }
    }

return 0;}