Witch Craft Moves

Time Limit : 3 sec, Memory Limit : 262144 KB

Problem K: Witch Craft Moves

Problem

会津魔法学校は、魔法を使える者が集る学校である。 会津魔法学校には1~Nまでの番号がついた教室と教室同士をつなぐ廊下がある。教室や廊下は何度でも通ることができる。また、会津魔法学校には任意の教室u,v間を0個以上の教室と廊下を一度ずつ通って移動することができるような経路がただ1つある。 各教室には魔法陣が設置してある。この魔方陣によって、教室に入る度に入った者の魔力が増減させられてしまうのだ。生徒の移動を助けるために以下の二つの質問に応えてほしい。

質問1
0 A B
教室AからBへ移動したときの魔力の残量を出力してほしい。教室ABでの増減も含む。また、この質問開始時点での魔力の量は毎回0である。

質問2
1 A C
教室Aの魔力の増減量がCだけ変動させる。

Input

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

入力の最初に教室の数Nが与えられる。続くN行に各教室に入ったときの魔力が増減する量が与えられる。i行目の値がi番の教室の情報に対応する。続くN-1行に廊下の情報が与えられる。j行目の廊下はaj番目とbj番目の教室をつなぐことを表す。次に質問の数Qが与えられる。続くQ行に上記の形式で質問が与えられる。

Output

各質問1について、答えを1行に出力せよ。

Constraints

入力は以下の条件を満たす。

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

Sample Input 1

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

Sample Output 1

16
18
31
33
16
16
18
1