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;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

class UnionFind
{
  public:
    UnionFind(int n)
        : mN(n)
    {
        REP(i, n)
        {
            mNodeTbl.push_back(i);
            mWaightTbl.push_back(0);
        }
    }

    int find(int x)
    {
        if (x == mNodeTbl[x])
            return x;

        int par = mNodeTbl[x];
        mNodeTbl[x] = find(mNodeTbl[x]);
        mWaightTbl[x] += mWaightTbl[par];
        return mNodeTbl[x];
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    ll waight(int x)
    {
        int y = find(x);
        return mWaightTbl[x] - mWaightTbl[y];
    }

    //! y bigger than x
    void unit(int x, int y, ll w)
    {
        int ox = x, oy = y;
        x = find(x);
        y = find(y);
        ll wx = mWaightTbl[ox];
        ll wy = mWaightTbl[oy];
        if (x == y)
            return;
        w = w + wx - wy;
        if (w < 0)
        {
            //! xにyをつなぐ
            mNodeTbl[y] = x;
            mWaightTbl[y] = mWaightTbl[x] - abs(w);
        }
        else
        {
            //! yにxをつなぐ
            mNodeTbl[x] = y;
            mWaightTbl[x] = mWaightTbl[y] - abs(w);
        }
    }

  private:
    int mN;
    vector<int> mNodeTbl;
    vector<ll> mWaightTbl;
};

int main()
{
    ll N, Q;
    cin >> N >> Q;
    UnionFind uf(N);
    REP(i, Q)
    {
        int c;
        cin >> c;
        if (c == 0)
        {
            ll x, y, z;
            cin >> x >> y >> z;
            uf.unit(x, y, z);
        }
        else if (c == 1)
        {
            ll x, y;
            cin >> x >> y;
            if (uf.same(x, y))
                cout << uf.waight(y) - uf.waight(x) << endl;
            else
                cout << '?' << endl;
        }
    }
    return 0;
}