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;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
#define fi first
#define se second
#define sc scanf
#define pr printf
#define pb push_back
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
using namespace std;
ll exp(ll a , ll b){
	if(b == 0)	return 1;
	int x = b % 2 == 0 ?   ((exp(a , b/2)%mod)*(exp(a , b / 2)%mod))%mod :  (a%mod*exp(a , b - 1) % mod)%mod;
	return x;
}
int parent[100005], value[100005] , size[100005];
void init(){
	for(int i = 0 ; i <= 100004 ; i++)
	{	
		parent[i] = i;
		size[i] = 1;
	}
}
int whoispar(int x){
		if(parent[x] == x)
			return x;
		else{
			int fx = parent[x];
			parent[x] = whoispar(parent[x]);
			value[x] += value[fx];
			return parent[x];
		} 
		return parent[x];
}
// union by size
void uni(int x , int y , int z){
	int parX = whoispar(x);
	int parY = whoispar(y);
	if(parX != parY){
		value[parX] = z + value[y] - value[x];
		parent[parX] = parY;
	}
}
int main(int argc,char ** argv){
	dhoom;
	int n , q; 
	cin >> n >> q;
	init();
	for(int i = 0 ; i < q ; i++){
		int c , l , r , z;
		cin >> c ;
		if(c == 0){
			cin >> l >> r >> z;
			uni(l , r , z);
			
		}
		else
		{
			cin >> l >> r;
			if(whoispar(l) == whoispar(r))
				cout << value[l] - value[r]  << endl;
			else 
				cout << "?" << endl;
		}
	}
	return 0;
	
}