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$.
