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;
 
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using ull = unsigned long long;
 
#define NL '\n'
#define xx first
#define yy second
#define ins insert
#define mp make_pair
#define pb push_back
#define sz(x) x.size()
#define pi 2.0*acos(0.0)
#define _ctz(x) __builtin_ctz(x)
#define _clz(x) __builtin_clz(x)
#define _pop(x) __builtin_popcount(x)
#define all(x) (x).begin(), (x).end()
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(ii,aa,bb) for(ll (ii)=ll(aa);(ii)<(ll)(bb);++(ii))
#define _fastIO() ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define _runtime() cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"1


const int N = 1e6+9;
int n, q, x, y, z, t;
vector<pii>parent(N);

void make_set(int v){ parent[v] = {v,0}; }

pii find_set(int v){
	if(v != parent[v].xx) {
		ll d = parent[v].yy;
		parent[v] = find_set(parent[v].xx);
		parent[v].yy += d;
	}
	return parent[v];
}

void union_set(int u, int v, ll w){
	pii du = find_set(u);
	pii dv = find_set(v);
	if(du.xx == dv.xx) return;
	if(du.yy >= w + dv.yy) {
		parent[dv.xx].xx = du.xx;
		parent[dv.xx].yy = du.yy - (w + dv.yy);
	}
	else {
		parent[du.xx].xx = dv.xx;
		parent[du.xx].yy = (w + dv.yy) - du.yy;
	}
}

int main(){
	_fastIO();
	cin >> n >> q;
	for(int i = 0; i < n; i++) make_set(i);
	for(int ix = 0; ix < q; ix++) {
		cin >> t;
		if(t == 0) {
			cin >> x >> y >> z;
			union_set(x, y, z);
		}
		else{
			cin >> x >> y;
			if(find_set(x).xx == find_set(y).xx) cout << (parent[x].yy - parent[y].yy) << NL;
			else cout << "?" << NL;
		}
	}
}