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 <iostream>

using namespace std;

struct set_type{
	int parent;
	int dif_with_parent;
};

set_type find(set_type subsets[], int i){
	if(subsets[i].parent != i){
		set_type parent_set = find(subsets, subsets[i].parent);
		subsets[i].dif_with_parent += parent_set.dif_with_parent;
		subsets[i].parent = parent_set.parent;
	}
	return subsets[i];
}

void unite(set_type subsets[], int x, int y, int dif){
	set_type xroot = find(subsets, x);
	set_type yroot = find(subsets, y);
	int root_dif = subsets[y].dif_with_parent - subsets[x].dif_with_parent + dif; // difference between yroot - xroot
	if(root_dif > 0){
		// yroot will be parent of xroot
		subsets[subsets[x].parent].dif_with_parent = root_dif;
		subsets[subsets[x].parent].parent = subsets[y].parent;
	}else{
		// xroot will be parent of yroot
		subsets[subsets[y].parent].dif_with_parent = -root_dif; 
		subsets[subsets[y].parent].parent = subsets[x].parent;
	}
}

int main(){
	int n, q;
	cin >> n >> q;
	set_type subsets[n];
	for(auto i = 0; i < n; ++i) subsets[i] = {i, 0};
	for(auto i = 0; i < q; ++i){
		int cmd_type;
		cin >> cmd_type;
		if(cmd_type == 0){
			int x, y, dif;
			cin >> x >> y >> dif;
			unite(subsets, x, y, dif);
		}else if(cmd_type == 1){
			int x, y;
			cin >> x >> y;
			find(subsets, x);
			find(subsets, y);
			if(subsets[x].parent != subsets[y].parent){
				cout << "?" << endl;
			}else{
				cout << subsets[x].dif_with_parent - subsets[y].dif_with_parent << endl;
			}
		}
	}
}