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 LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()

//重み付きUnion-Find木(ランク無し)
struct UnionFind{
private:
	vector<int> parent;
	vector<long long> difference;
public:
	void init(int N){ //初期化する O(N)
		parent.clear();
		difference.clear();
		for(int i=0; i<N; i++){
			parent.push_back(i);
			difference.push_back(0);
		}
	}
	int root(int a){ //親を返す O(log N)
		if(parent[a] == a) return a;
		int r = root(parent[a]);
		difference[a] += difference[parent[a]];
		return parent[a] = r;
	}
	void unite(int a, int b, long long x){ //木を併合する x=a-b O(log N)
		int rootA = root(a);
		int rootB = root(b);
		if(rootA != rootB){
			x += weight(b);
			x -= weight(a);
			parent[rootA] = rootB;
			difference[rootA] = x;
		}
	}
	bool same(int a, int b){ //属する木が同じかを返す O(log N)
		return root(a) == root(b);
	}
	long long weight(int a){
		root(a); //経路圧縮
		return difference[a];
	}
	long long diff(int a, int b){ //重みの差を返す O(log N)
		return weight(a) - weight(b);
	}
};

int main(){
	
	int N,Q;
	cin >> N >> Q;
	UnionFind uf;
	uf.init(N);
	for(int i=0; i<Q; i++){
		int c;
		cin >> c;
		if(c == 0){
			int x,y,z;
			cin >> x >> y >> z;
			uf.unite(x,y,z);
		}
		else{
			int x,y;
			cin >> x >> y;
			if(uf.same(x,y)) cout << uf.diff(x,y) << endl;
			else cout << "?" << endl;
		}
	}

	return 0;
}