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>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;

class UnionFind{
public:
	vector<ll> par;
	vector<ll> d;
	//0-indexed
	UnionFind(ll n){
		init(n);
	}
	void init(ll n = 1) {
		par.resize(n);
		d.resize(n,0);
		for (ll i = 0; i < n; ++i) par[i] = i;
	}
	ll len1(ll x){
		if(par[x]==x)return 0;
		ll ans = d[x];
		ans += len1(par[x]);
		return ans;
	}
	ll root(ll x = 1){
		if(par[x]==x)return x;
		else{
			d[x] = len1(par[x]) + d[x];
			return par[x] = root(par[x]);
		}
	}
	ll length(ll x,ll y){ // xから右にlengthいったところにy
		return len1(y) - len1(x);
	}
	void unite(ll x,ll y,ll dd){ // xから右にdだけ離れたところにy
		dd += len1(x);x=root(x);
		dd -= len1(y);y=root(y);
		if(x==y)return;
		if(dd>=0){
			d[y] = dd;
			par[y] = x;
		}else{
			d[x] = -dd;
			par[x] = y;
		}
	}
};
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll N,Q,a,x,y,z;
	cin >> N >> Q;
	UnionFind uf(N);
	FOR(i,0,Q){
		cin >> a;
		if(a==0){
			cin >> x >> y >> z;
			uf.unite(x,y,z);
		}else{
			cin >> x >> y;
			if(uf.root(x)!=uf.root(y)){
				cout << "?" << endl;
			}else{
				cout << uf.length(x,y) << endl;
			}
		}
	}
}