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

using namespace std;

struct w_unionfind {
    using diff_from = pair<int, int>;
    using result = pair<int, bool>;
    
    vector<diff_from> uf;
    
    w_unionfind(int n) : uf(n) {
        for(int i=0; i<n; i++) uf[i] = diff_from(i, 0);
    }
    
    int root(int i) {
        if(uf[i].first==i) return i;
        int r = root(uf[i].first);
        uf[i] = diff_from(r, uf[i].second + uf[uf[i].first].second);
        return r;
    }
    
    void relate(int i, int j, int d) {
        int ri = root(i);
        int rj = root(j);
        if(ri != rj) {
            uf[rj] = diff_from(ri, uf[i].second + d - uf[j].second);
        }
    }

    result diff(int i, int j) {
        int ri = root(i);
        int rj = root(j);
        if(ri != rj) return result(0, false);
        return result(uf[j].second - uf[i].second, true);
    }
    
};

int main() {
    int n, q;
    cin >> n >> q;
    w_unionfind uf(n);
    while(q--) {
        int c;
        cin >> c;
        if(c) {
            int x, y;
            cin >> x >> y;
            auto&& r = uf.diff(x, y);
            if(r.second) cout << r.first << endl;
            else cout << "?" << endl;
        } else {
            int x, y, z;
            cin >> x >> y >> z;
            uf.relate(x, y, z);
        }
    }
    return 0;
}