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 debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

#ifndef UNION_FIND_TREE
#define UNION_FIND_TREE
template<typename T>
class UnionFindTree{
	private:
		int N;
		vector<int> parent, rank, size;
		vector<T> diff_weight;

	public:
		void init(){
			for(int i = 0; i < (int) N; i++){
				parent[i] = i; rank[i] = 0; size[i] = 1; diff_weight[i] = 0;
			}
		}

		UnionFindTree(int N): N(N), parent(N), rank(N), size(N), diff_weight(N){
			init();
		}

		int root(int x){
			if(parent[x] == x){
				return x;
			}else{
				int r = root(parent[x]);
				diff_weight[x] += diff_weight[parent[x]];
				return parent[x] = r;
			}
		}

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

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

		// weight(y) = weight(x) + w となるようにmergeする
		bool unite(int x, int y, T w = 0){
			w += weight(x); w -= weight(y);
			x = root(x); y = root(y);
			if(x == y) return weight(y) - weight(x) == w;

			if(rank[x] < rank[y]){
				swap(x, y);
				w = -w;
			}

			parent[y] = x;
			size[x] += size[y];
			if(rank[x] == rank[y]) rank[x]++;
			diff_weight[y] = w;
			return true;
		}

		bool isSame(int x, int y){
			return root(x) == root(y);
		}
		
		int count(int x){
			return size[root(x)];
		}
};
#endif


int main(void){
	int n, q;
	cin >> n >> q;

	UnionFindTree<int> ut(n);
	vector<string> vec;
	for(int i = 0; i < q; i++){
		int k;
		cin >> k;
		if(k){
			int x, y;
			cin >> x >> y;
			vec.push_back(ut.isSame(x, y) ? to_string(ut.diff(x, y)) : "?");
		}else{
			int x, y, z;
			cin >> x >> y >> z;
			ut.unite(x, y, z);
		}
	}

	for(auto res: vec) cout << res << '\n';

	return 0;
}