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 JAVA):

Solution:


import java.util.Scanner;

public class Main {
	private static final int INF = Integer.MAX_VALUE;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
				Scanner sc = new Scanner(System.in);
				int n = 0;
				int op_num = 0;
				n  = sc.nextInt();
				op_num = sc.nextInt();
				String[] op = new String[op_num+1];
				for (int i = 0 ; i < op.length; i++) {
					op[i] = sc.nextLine();
				}
				//get datag
				int[][] data = new int[op_num][3];
				for (int i = 1, n1 =0; i<= op_num; i++,n1++) {
					if(data[n1][0] == 0) {
						String[] Split = op[i].split(" ");
						data[n1] = new int[Split.length];
						for(int j = 0;j<Split.length;j++)
							data[n1][j] = Integer.parseInt(Split[j]);
					}else {
						String[] Split = op[i].split(" ");
						data[n1] = new int[Split.length];
						for(int j = 0;j<Split.length;j++)
							data[n1][j] = Integer.parseInt(Split[j]);
					}
				}
				
				
				
				
				
				
				//Operate data
				Set2 set = new Set2(n);
				set.makeset();
				
				for(int i= 0 ;i < data.length;i++ ) {
					if(data[i][0] == 0) {
						int x = data[i][1];
						int y = data[i][2];
						int z = data[i][3];
						set.link(x, y, z);	
					}
					else if(data[i][0] == 1){
						int x = data[i][1];
						int y = data[i][2];
						
						if(set.findset(x)== set.findset(y))
							System.out.println(set.we[y] - set.we[x]);
						else 
							System.out.println("?");
					}
					
				}
	}
}


class Set2{

	int[] rank,parent;
	int n;
	int weight;
	int[] we;
	int index;
	private static final int INF = Integer.MAX_VALUE;
	
	
	public Set2(int n) {
		rank = new int[n];
		parent = new int[n];
		we = new int[n];
		this.n = n;
		makeset();
	}
	
	void makeset() {
		for(int i= 0 ; i< n; i++)
			parent[i] = i;
	}
	
	int findset(int x) {
		int y = 0;
		if (x == parent[x])
			return x;
		else {
			int temp = parent[x];
			parent[x] = findset(parent[x]);
			we[x] += we[temp]; 
			return parent[x];
		}
	}
	
	void link(int x, int y, int z) {
		int a = findset(x);
		int b = findset(y);
		//int c = findset(z);
		
		if(a!=b) {
			parent[b] = a;
			we[b] = we[x] - we[y] + z;
		}
	}
	
	
	
	
	
	
	
	
	
	
	
	
	

}