And Queries

You are given a weighted tree with $N$ nodes numbered from $0$ to $N-1$.

Let $cost(u, v)$ denote the bitwise AND of all edge weights on the shortest path between nodes $u$ and $v$.

The cost of the tree is the sum of $cost(u, v)$ across all $0 \le u < v < N$. More formally, the cost of the tree is:

Task

You have to process $Q$ queries described by a triplet of integers $U_j$, $V_j$, $X_j$: the weight of the edge connecting nodes $U_j$ and $V_j$ changes to $X_j$.

Print the cost of the tree before the first query and following each query.

Input data

The first line of the input contains a single integer $N$, the number of nodes in the tree.

Each of the next $N-1$ lines contains 3 integers $A_i$, $B_i$ and $W_i$, representing an edge between nodes $A_i$ and $B_i$ with weight $W_i$.

The next line contains a single integer $Q$, the number of queries.

Each of the next $Q$ lines contains 3 integers $U_j$, $V_j$ and $X_j$, describing a query.

Output data

Print $Q+1$ integers, the cost of the tree before the first query, and after each query.

Constraints and clarifications

• $2 \le N \le 100 \ 000$
• $0 \le A_i, B_i < N$ for each $i=0\ldots N-2$
• The edges form a tree graph.
• $0 \le W_i < 2^{30}$ for each $i=0\ldots N-2$
• $1 \le Q \le 100 \ 000$
• $0 \le U_j, V_j < N$ and there is an edge between nodes $U_j$ and $V_j$ for each $j=0\ldots Q-1$.
• $0 \le X_j < 2^{30}$ for each $j=0\ldots Q-1$

Example 1

stdin

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

stdout

9 7 15

Explanation

In this sample case:

• Before the first query, the cost of the tree is $cost(0,1)+cost(0,2)+cost(0,3)+cost(1,2)+cost(1,3)+cost(2,3)=1+2+3+(1 \& 2)+ (1 \& 3) + (2 \& 3)=1+2+3+0+1+2=9$.
• After the first query, the cost of the tree is $cost(0,1)+cost(0,2)+cost(0,3)+cost(1,2)+cost(1,3)+cost(2,3)=1+2+4+(1 \& 2)+ (1 \& 4) + (2 \& 4)=1+2+4+0+0+0=7$.
• After the second query, the cost of the tree is $cost(0,1)+cost(0,2)+cost(0,3)+cost(1,2)+cost(1,3)+cost(2,3)=1+5+4+(1 \& 5)+ (1 \& 4) + (5 \& 4)=1+5+4+1+0+4=15$.

Example 2

stdin

7
0 1 0
0 2 0
1 3 1
1 4 0
2 5 0
5 6 1
5
0 2 1
1 4 1
0 2 1
2 5 1
0 1 1

stdout

2 3 5 5 9 21

Example 3

stdin

8
0 1 1
0 2 1
1 3 1
1 4 1
2 5 1
5 6 0
6 7 1
4
1 3 0
5 6 0
0 2 0
6 7 0

stdout

16 11 11 5 4

Example 4

stdin

6
0 1 11
1 2 6
2 3 15
3 4 13
4 5 7
3
1 2 14
2 3 10
3 4 6

stdout

93 141 114 96

Example 5

stdin

10
6 4 1
4 8 1
4 7 1
3 8 0
3 9 1
5 9 1
0 8 1
8 2 1
7 1 1
7
7 4 0
8 3 1
9 3 0
9 5 0
4 7 1
1 7 1
3 9 1

stdout

24 14 29 17 16 28 28 36

Example 6

stdin

10
7 8 57060341
7 6 912175869
4 9 722659129
1 6 1070069467
4 2 1054506724
4 3 803713203
0 6 1042268623
5 0 430394330
3 6 761326510
7
5 0 759019469
6 1 737763327
7 8 186596588
4 3 494827354
3 6 930475517
4 3 389510846
6 1 737763327

stdout

24048471575 27735341590 26470706958 26585373193 17345134615 17809394976 17976445112 17976445112