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;

#define int long long
#define endl '\n'
const int N = 1e5 + 10;
int par[N], cost[N], sz[N];

void init(int n) {
    for (int i = 0; i < n; i++)
        par[i] = i, sz[i] = 1;
}

int find(int x) {
    int prep = par[x];
    if (x != par[x]) {
        par[x] = find(par[x]);
    }
    cost[x] += cost[prep];
    return par[x];
}


void unite(int u, int v, int wt) {
    int par1 = find(u), par2 = find(v);

    if (par1 == par2)
        return;
    int c = wt + cost[u] - cost[v];
    if (sz[par1] >= sz[par2]) {
        par[par2] = par1;
        cost[par2] = c;
        sz[par1] += sz[par2];
    } else {
        par[par1] = par2;
        cost[par1] = -c;
        sz[par2] += sz[par1];
    }
}

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

    init(n);

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

        if (type == 0) {
            int x, y, z;
            cin >> x >> y >> z;

            unite(x, y, z);
        } else {
            int x, y;
            cin >> x >> y;

            if (find(x) == find(y))
                cout << cost[y] - cost[x] << endl;
            else
                cout << "?" << endl;
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}