当前没有测试数据。

题目描述

CNZ lives in the forest, and he has energy stones, numbered from to . CNZ need to eat energy generated by energy stones.

The energy stone initially contains EiE_iEi​ units of energy and will increase LiL_iLi​ units of energy each second. The maximum energy of energy stone is CiC_iCi​, the stone's energy stops increasing once it reach CiC_iCi​.

Each time he absorbs the energy of a continuous interval of stone. For example, if CNZ absorbs the energy of [S, T] stones, all energy stones numbered from to will become zero units of energy. CNZ can get the sum of energy in this range.

CNZ will eat times. The i-th eating happens after tit_iti​ seconds, and eat interval is [Si,Ti][S_i, T_i][Si​,Ti​].

What's the total amount of energy CNZ has eaten after eating.

输入格式

The first line of the input gives the number of test cases, $T\ (T \leq 20)T$. test cases follow. Each test case starts with a line containing the integer $\ (1 \leq N \leq 10^5)$, the number of energy stones. Then, there are more lines, the i-th of which contains the three integers EiE_iEi​, LiL_iLi​ and CiC_iCi​ as described above. The next line contains one integer M. Then, there are more lines, the i-th of which contains the three integers tit_iti​, SiS_iSi​ and TiT_iTi​ as described above.

Limits: $1 \leq N \leq 10^5$

$0 \leq E_i \leq C_i \leq 10^6$

$0 \leq L_i \leq 10^6$

$0 < M \leq 10^5$

$0 < t_i \leq 2 \times 1$

$t_{i-1} < t_i$ ​ $1 \leq S_i \leq T_i \leq N$

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the result.

样例

样例输入 1

1
4
2 1 4
2 2 5
2 1 10
2 3 2
2
1 1 4
4 2 3

样例输出 1

Case #1: 20