Apples

The people in city A want to share their apples. There are $n$ people in city A, and they are numbered from $1$ to $n$. The $i$-th person has $b_i$ apples initially, and this person will be happy if and only if he/she has exactly $e_i$ apples after sharing.It is guaranteed that the total number of apples will not changed, which is $\sum_{i=1}^n b_i=\sum _{i=1}^n e_i$.

The city has $n$ undirected roads. The $i$-th road connects the $i$-th and the $(i\bmod n+1)$-th person’s house. the apples can be transported by these roads.
Each road has a value $l_i$, denoting the cost of transporting a single apple from person $i$ to $(i\bmod n+1)$ or from person $(i\bmod n+1)$ to $i$. 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\le 100)$ - the number of test cases.

For each test case:

The first line contains a single integer $n(2\le n \le 5\times 10^5)$ - the number of people.

From the second line to the $(n+1)$-th line, each line contains three integers $b_i,e_i,l_i(0\le b_i,e_i \le 10^9,0\le l_i \le 10^4)$. It is guaranteed that $\sum_{i=1}^n b_i=\sum_{i=1}^n e_i\le 10^9$.

The $(n+2)$-th line contains a single integer $q(0\le q \le 5\times 10^5)$.

Then the next $q$ lines, each line contains two integers $x,y(1\le x \le n,0\le y \le 10^4)$, 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 10^6$.

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\le i \le 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 1

23
1
2
2
1

2022“杭电杯”中国大学生算法设计超级联赛（10）