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>
#define MAX 100010
#define inf 1<<29
#define linf (1e16)
#define eps (1e-8)
#define Eps (1e-12)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

int n,q;
int p[MAX],cost[MAX];

void init(){
  FOR(i,0,n){ p[i]=i;cost[i]=0; }
}

pii f(int a){
  if(p[a]==a)return mp(a,0);
  pii res=f(p[a]);
  res.s+=cost[a];
  p[a]=res.f;
  cost[a]=res.s;
  return res;
}

void relate(int a,int b,int c){
  pii d=f(a),e=f(b);
  p[d.f]=e.f;
  cost[d.f]=c-d.s+e.s;
}

void diff(int a,int b){
  pii d=f(a),e=f(b);
  if(d.f!=e.f)cout<<"?"<<endl;
  else cout<<d.s-e.s<<endl;
}

int main()
{
  cin>>n>>q;
  init();
  FOR(i,0,q){
    int a,b,c,d;
    cin>>a;
    if(a==0){
      cin>>b>>c>>d;
      relate(b,c,d);
    }
    else {
      cin>>b>>c;
      diff(b,c);
    }
  }
  return 0;
}