Problem: Problem

Aizu Magic School is a school where people who can use magic gather. Aizu Magic School has classrooms numbered from 1 to N and a corridor connecting the classrooms. You can go through the classrooms and corridors as many times as you like. In addition, Aizu Magic School has only one route that allows you to move between any classroom u and v through 0 or more classrooms and a corridor once. A magic circle is set up in each classroom. This magic square increases or decreases the magical power of those who enter the classroom each time they enter the classroom. Please answer the following two questions to help the students move.

question 1
0 A B
I want you to output the remaining amount of magical power when you move from classroom A to B. Including increase / decrease in classrooms A and B. Also, the amount of magical power at the beginning of this question is 0 each time.

Question 2
1 A C
The amount of increase / decrease in the magical power of classroom A changes by C.

Constraints

The input satisfies the following conditions.

* 1 ≤ N ≤ 2000
* 1 ≤ Ai ≤ 2000
* 1 ≤ Bi ≤ 2000
* 1 ≤ aj, bj ≤ N
* 1 ≤ Q ≤ 1000000
* -10000 ≤ Ci ≤ 10000

Input


N
cost1
::
costN
a1 b1
::
aN-1 bN-1
Q
query1
::
queryQ


The number N of classrooms is given at the beginning of the input. The following N lines are given the amount of magical power that increases or decreases when entering each classroom. The value on the i-line corresponds to the information in the classroom on the i-th line. Corridor information is given to the following N-1 line. The corridor on the jth line represents connecting the ajth and bjth classrooms. Then the number of questions Q is given. The following Q line is given the question in the above format.

Output

Output the answer to one line for each question 1.

Example

Input

7
1
2
3
4
5
6
7
1 2
1 3
3 4
3 5
5 6
5 7
10
0 1 7
0 2 7
1 1 15
0 1 7
0 2 7
0 1 1
1 1 -15
0 1 7
0 2 7
0 1 1


Output

16
18
31
33
16
16
18
1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;




#define NUM 2005

int N = 1;
int num_node;
int root = 0,euler_index = 0;
int MAX_LOG_V = 13;
int LEFT[NUM],RIGHT[NUM];


int parent[13][NUM],depth[NUM];
vector<int> G[NUM];
ll W[NUM],sum_W[NUM];
ll uniformity[8*NUM],partial[8*NUM];


//★★開区間なので注意★★

void init(ll first_N){
	while(N < first_N)N *= 2;
}

void add(ll left,ll right,ll value,ll node_id,ll node_left,ll node_right){

	if(right <= node_left || left >= node_right)return;
	else if(left <= node_left && right >= node_right){
		uniformity[node_id] += value;
	}else{
		partial[node_id] += (min(right,node_right)-max(left,node_left))*value;
		add(left,right,value,2*node_id+1,node_left,(node_left+node_right)/2);
		add(left,right,value,2*node_id+2,(node_left+node_right)/2,node_right);
	}
}

ll getSum(ll left,ll right,ll node_id,ll node_left,ll node_right){
	if(right <= node_left || left >= node_right)return 0;
	else if(left <= node_left && right >= node_right){
		return (node_right-node_left)*uniformity[node_id]+partial[node_id];

	}else{
		ll sum = (min(right,node_right)-max(left,node_left))*uniformity[node_id];

		sum += getSum(left,right,2*node_id+1,node_left,(node_left+node_right)/2);
		sum += getSum(left,right,2*node_id+2,(node_left+node_right)/2,node_right);
		return sum;
	}
}


void dfs(int node_id,int parent_id,int DEPTH,ll total_W){

	parent[0][node_id] = parent_id;
	depth[node_id] = DEPTH;
	LEFT[node_id] = euler_index++;
	sum_W[node_id] = total_W+W[node_id];

	for(int i = 0; i < G[node_id].size(); i++){
		if(G[node_id][i] == parent_id)continue;
		dfs(G[node_id][i],node_id,DEPTH+1,sum_W[node_id]);
	}
	RIGHT[node_id] = euler_index++;
}

//初期化
void init_lca(){

	dfs(root,-1,0,0);

	for(int k = 0; k + 1 < MAX_LOG_V; k++){
		for(int node_id = 0; node_id < num_node; node_id++){
			if(parent[k][node_id] < 0)parent[k+1][node_id] = -1; //node_idの2^k上のノードがルートノードより上なら、2^(k+1)上も同様とする
			else{
				parent[k+1][node_id] = parent[k][parent[k][node_id]];
			}
		}
	}
}

int lca(int left,int right){

	if(depth[left] > depth[right])swap(left,right);
	for(int k = 0; k < MAX_LOG_V; k++){
		if((depth[right]-depth[left]) >> k & 1){
			right = parent[k][right];
		}
	}
	if(left == right)return left;

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(parent[k][left] != parent[k][right]){
			left = parent[k][left];
			right = parent[k][right];
		}
	}
	return parent[0][left];
}

int main(){

	scanf("%d",&num_node);

	for(int i = 0; i < num_node; i++){

		scanf("%lld",&W[i]);
	}


	int from,to;

	for(int i = 0; i < num_node-1; i++){

		scanf("%d %d",&from,&to);
		from--;
		to--;

		G[from].push_back(to);
		G[to].push_back(from);
	}

	init_lca();

	int first_N = RIGHT[root]+1; //セグ木における最下層のノードは、最低RIGHT[0]+1個あれば良い(+1は0オリジンのため)

	init(first_N);

	for(ll i = 0; i <= 2*N-2; i++){
		uniformity[i] = 0;
		partial[i] = 0;
	}

	int num_query;
	scanf("%d",&num_query);

	int command;

	ll A,B,LCA;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d %lld %lld",&command,&A,&B);

		if(command == 0){

			A--;
			B--;
			LCA = lca(A,B);

			ll cost_A = sum_W[A] + getSum(LEFT[A],LEFT[A]+1,0,0,N);
			ll cost_B = sum_W[B] + getSum(LEFT[B],LEFT[B]+1,0,0,N);
			ll cost_LCA = sum_W[LCA] + getSum(LEFT[LCA],LEFT[LCA]+1,0,0,N);

			printf("%lld\n",cost_A+cost_B-2*cost_LCA+W[LCA]);

		}else{

			A--;
			add(LEFT[A],RIGHT[A]+1,B,0,0,N);
			W[A] += B;
		}
	}

	return 0;
}