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>

template <typename T>
class Nullable {
	T* _value{ nullptr };
	Nullable() {};
	Nullable(T *own_ptr) :_value{ own_ptr } {}
public:
	~Nullable() { delete _value; }
	static Nullable make_nullable(const T &value) {
		return Nullable(new T(value));
	}
	static Nullable make_null() {
		return Nullable();
	}
	const T &value() const {
		return *_value;
	}
	bool operator==(const void *ptr) const {
		return _value == ptr;
	}
};
template<typename T>
bool operator==(const void *ptr, Nullable<T> &nullable) {
	return nullable == ptr;
}
class Weighted_union_find_tree {
	struct Pair {
		Weighted_union_find_tree *ptr;
		int differ;
	};
	Weighted_union_find_tree *_parent{ nullptr };
	int _diff{ 0 };
	Pair parent() {
		if (_parent == nullptr)
			return Pair{ this, 0 };
		else
		{
			auto prev = _parent->parent();
			_parent = prev.ptr;
			_diff += prev.differ;
			return Pair{ _parent, _diff };
		}
	};
public:
	void set_relate(Weighted_union_find_tree &greater, int weight) {
		if (is_related(greater)) return;
		auto other_pos = greater.parent();
		other_pos.ptr->_parent = this;
		other_pos.ptr->_diff = weight - other_pos.differ;
	};
	bool is_related(Weighted_union_find_tree &other) {
		return parent().ptr == other.parent().ptr;
	};
	Nullable<int> diff(Weighted_union_find_tree &other) {
		if (!is_related(other)) return Nullable<int>::make_null();
		auto pos = parent();
		auto other_pos = other.parent();
		return Nullable<int>::make_nullable(other_pos.differ - pos.differ);
	};
};
int main() {
	int n, q;
	std::cin >> n >> q;
	std::vector<Weighted_union_find_tree> uft(n);
	int query, x, y, z;
	for (auto i = 0; i < q; ++i) {
		std::cin >> query;
		switch (query) {
		case 0: std::cin >> x >> y >> z;
			uft[x].set_relate(uft[y], z); break;
		default: std::cin >> x >> y;
			auto nullable = uft[x].diff(uft[y]);
			if (nullable == nullptr) {
				std::cout << '?' << std::endl;
			}
			else {
				std::cout << nullable.value() << std::endl;
			}
		}
	}
}