Problem Description

Giving a tree with weight on edges and weight on points, for every pairs of points $( i, j ) ( i < j )$, we can calculate the cost as $(a_i$ xor $a_j) \times dis(i,j)$, $dis(i,j)$ means the distance between point $i$ and point $j$.

There are $T$ operations, each operation the weight of a point will be modified. Please output the sum of cost for each pairs after every operations.

Input

Several test cases(about $3$)

For each cases, first come an integer, $n(1 \leq n \leq 30000)$,indicating the number of nodes in the tree.

Then follows $n$ integers $a_i ( 0 \leq a_i \leq 16383)$

Next $n - 1$ lines,input three numbers $A_i, B_i, C_i (0 \leq C_i \leq 100)$ per line,indicating a long for $C_i$ edge connecting $A_i$ and $B_i$.

Then input an integer $T(1 \leq T \leq 30000)$.

Next $T$ lines,input two numbers $D_i,E_i ( 1 \leq D_i \leq n, 0 \leq E_i \leq 16383)$,indicating the $aD_i$ is modified to $E_i$.

Output

For each cases, please output $T$ answers.

5
1 2 3 4 5
1 2 3
1 3 4
2 4 5
2 5 5
5
1 2
2 4
3 2
4 1
5 5

346
346
335
330
330