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 REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class UnionFind{
	vector<ll> rank;
	vector<ll> diff_weight;
	vector<ll> num;
public:
	vector<ll> par;

	UnionFind(ll N):par(N),num(N),rank(N),diff_weight(N){
		for(ll i=0;i<N;i++){
			par[i]=i;
			num[i]=1;
			rank[i]=0;
			diff_weight[i]=0;
		}
	}

	ll root(ll x){
		if(par[x]==x){
			return x;
		}
		ll r = root(par[x]);
		diff_weight[x]+=diff_weight[par[x]];
		return par[x]=r;
	}

	void unite(ll x,ll y){
		ll rx = root(x);
		ll ry = root(y);
		if (rx == ry) return;
		if(rank[rx]<rank[ry]) swap(rx,ry);
		if(rank[rx]==rank[ry]) ++rank[rx];
		par[ry] = rx;
		num[rx] += num[ry];
	}

	void relate(ll x,ll y,ll w){
		w+=weight(x),w-=weight(y);
		ll rx = root(x);
		ll ry = root(y);
		if (rx == ry) return;
		if(rank[rx]<rank[ry]){
			swap(rx,ry);
			w = -w;
		}
		if(rank[rx]==rank[ry]) ++rank[rx];
		par[ry] = rx;
		diff_weight[ry] = w;
		num[rx] += num[ry];
	}

	bool same(ll x,ll y){
		ll rx = root(x);
		ll ry = root(y);
		return rx == ry;
	}

	ll getsize(ll x){
		return num[root(x)];
	}

	ll weight(ll x){
		root(x);
		return diff_weight[x];
	}

	ll diff(ll x,ll y){
		return weight(y)-weight(x);
	}
};


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	auto N=in(),Q=in();
	UnionFind uf(N);

	REP(i,Q){
		int q=in();
		int u=in(),v=in();
		if(q==1){
			if(uf.same(u,v)){
				out(uf.diff(u,v));
			}
			else{
				out('?');
			}
		}
		else{
			int w=in();
			uf.relate(u,v,w);
		}
	}
	
	return 0;
}