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>
#include <vector>
#include <iomanip>
using namespace std;

class PotentialUnionFind {

private:
	vector<int> nums;
	vector<int> weights;
	vector<int> rank;

public:
	PotentialUnionFind(int n) : weights(vector<int>(n, 0)), rank(vector<int>(n, 0)) {
		for (int i = 0; i < n; ++i) {
			nums.push_back(i);
		}

	}

	int find(int x) {

		if (nums[x] == x)
			return x;

		int root = find(nums[x]);
		weights[x] += weights[nums[x]];
		return nums[x] = root;

	}

	bool isSame(int x, int y) {
		return find(x) == find(y);
	}

	void unit(int x, int y, int w) {

		int x_root = find(x);
		int y_root = find(y);

		w += weights[x];
		w -= weights[y];

		if (rank[x_root] < rank[y_root]) {
			swap(x_root, y_root);
			w *= -1;
		}
		else if (rank[x_root] == rank[y_root])
			++rank[x_root];

		nums[y_root] = x_root;
		weights[y_root] = w;

	}

	int diff(int x, int y) {
		return weights[y] - weights[x];
	}


	void print() {


		for (int i = 0; i < nums.size(); ++i) {
			cout << setw(4) << i << " ";

		}
		cout << endl;

		for (int i = 0; i < nums.size(); ++i) {
			cout << setw(4) << nums[i] << " ";
		}
		cout << endl;

		for (int i = 0; i < weights.size(); ++i) {
			cout << setw(4) << weights[i] << " ";
		}
		cout << endl << endl;
	}
};

int main() {

	int n, q;

	cin >> n >> q;

	PotentialUnionFind tree(n);

	for (int i = 0; i < q; ++i) {

		int com, x, y, z;
		cin >> com >> x >> y;

		switch (com) {

		case 0:
			cin >> z;
			tree.unit(x, y, z);
			break;

		case 1:
			if (tree.isSame(x, y))
				cout << tree.diff(x, y) << endl;
			else
				cout << "?" << endl;
			break;

		}

		// cout << x << " " << y << " " << z << endl;
		// tree.print();
	}

	return 0;

}