The people in city A want to share their apples. There are nn people in city A, and they are numbered from 1 to n. The ii-th person has bi apples initially, and this person will be happy if and only if he/she has exactly ei apples after sharing.It is guaranteed that the total number of apples will not changed, which is
∑i=1nbi=∑i=1nei.
The city has n undirected roads. The i-th road connects the i-th and the (i modn+1)-th person’s house. the apples can be transported by these roads. Each road has a value li, denoting the cost of transporting a single apple from person i to (i modn+1) or from person (i modn+1) to ii. Each apple can be transported by any road any number of times(including zero).
You need to find out a way to make all the people become happy and minimize the total cost of all the apples. And the cost of an apple is the total cost of all the roads it passed. Noted that an apple can pass the same road more than one time, and the cost will be counted repeatedly.
The cost of some roads may be changed, and you need to find out all the answers.
The first line contains a single integer T(T≤100) - the number of test cases.
For each test case:
The first line contains a single integer n(2≤n≤5×105) - the number of people.
From the second line to the (n+1)-th line, each line contains three integers bi,ei,li(0≤bi,ei≤109,0≤li≤104). It is guaranteed that∑i=1nbi=∑i=1nei≤109.
The (n+2)-th line contains a single integer q(0≤q≤5×105).
Then the next q lines, each line contains two integers x,y(1≤x≤n,0≤y≤104), means that l_x is changed to y. Please note that the change in l_x has aftereffects.
It is guaranteed that the sum of n and the sum of q do not exceed 2\times 2×106.
For each test case, output (q+1) lines:
Each line contains a single integer, The first integer denotes the answer without any changing, and the (i+1)-th integer (1≤i≤n) denotes the answer after the i-th change.
2
4
4 1 4
5 1 4
1 9 1
9 8 1
0
2
1 2 1
2 1 2
3
1 3
1 2
2 123
1
2
2
1