A 市的居民们想要分享他们的苹果。A 市共有 $n$ 名居民，编号为 $1$ 到 $n$。第 $i$ 名居民初始拥有 $b_i$ 个苹果，当且仅当分享后他/她恰好拥有 $e_i$ 个苹果时，他/她才会感到高兴。题目保证苹果总数不变，即 $\sum_{i=1}^n b_i = \sum_{i=1}^n e_i$。

该市有 $n$ 条无向道路。第 $i$ 条道路连接第 $i$ 名居民和第 $(i \pmod n + 1)$ 名居民的住所。苹果可以通过这些道路运输。每条道路都有一个权值 $l_i$，表示将一个苹果从第 $i$ 名居民处运输到第 $(i \pmod n + 1)$ 名居民处（或反之）的成本。每个苹果可以通过任何道路任意多次（包括零次）。

你需要找到一种方法，使得所有居民都感到高兴，并最小化所有苹果运输的总成本。一个苹果的成本是它所经过的所有道路的成本之和。注意，一个苹果可以多次经过同一条道路，且成本会重复计算。

部分道路的权值可能会发生改变，你需要求出所有情况下的答案。

输入格式

第一行包含一个整数 $T(T \le 100)$，表示测试用例的数量。

对于每个测试用例： 第一行包含一个整数 $n(2 \le n \le 5 \times 10^5)$，表示居民人数。 从第二行到第 $(n+1)$ 行，每行包含三个整数 $b_i, e_i, l_i(0 \le b_i, e_i \le 10^9, 0 \le l_i \le 10^4)$。保证 $\sum_{i=1}^n b_i = \sum_{i=1}^n e_i \le 10^9$。 第 $(n+2)$ 行包含一个整数 $q(0 \le q \le 5 \times 10^5)$。 接下来的 $q$ 行，每行包含两个整数 $x, y(1 \le x \le n, 0 \le y \le 10^4)$，表示 $l_x$ 被修改为 $y$。请注意，$l_x$ 的修改具有累积效应。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，输出 $(q+1)$ 行： 每行包含一个整数。第一个整数表示没有任何修改时的答案，第 $(i+1)$ 个整数 $(1 \le i \le q)$ 表示第 $i$ 次修改后的答案。

样例

输入格式 1

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

输出格式 1

23
1
2
2
1