题目内容

充电场站财务侧维护一条周转金账户。巡检员按固定顺序接待 $K$ 位车主，账户初始持有若干非负整数周转金。

对第 $i$ 位车主（$1\le i\le K$），登记三项参数：

• $F_i$：对方资金水位；
• $R_i$：若账户回流，对方拨付给账户的金额；
• $P_i$：若账户拨付，账户付给对方的金额。

接待规则如下：

1. 若 $F_i<\text{当前周转金}$：账户拨付 $P_i$，周转金减少 $P_i$；若当前不足 $P_i$，则变为 $0$。
2. 若 $F_i\ge\text{当前周转金}$：对方拨付 $R_i$ 给账户，周转金增加 $R_i$（保证 $R_i\le F_i$）。

共有 $T$ 次核算询问。每次给出一个初始周转金 $s_j$，求接待完全部 $K$ 位车主后账户的周转金。

输入描述

第一行一个整数 $K$，表示车主人数。

接下来 $K$ 行，每行三个整数 $F_i,R_i,P_i$，表示第 $i$ 位车主的资金水位、回流金额与拨付金额。

接下来一行一个整数 $T$，表示询问次数。

接下来 $T$ 行，每行一个整数 $s_j$，表示第 $j$ 次询问的初始周转金。

输出描述

对每个询问输出一行一个整数，表示接待结束后的周转金。

样例1

输入

3
12 4 2
18 6 3
14 5 2
5
0
8
12
16
20

输出

15
16
20
18
22

说明

以初始周转金 $12$ 为例：

1. 第 $1$ 位 $F_1=12$，当前 $12$，$12\ge 12$，回流 $4$，变为 $16$。
2. 第 $2$ 位 $F_2=18$，当前 $16$，$18\ge 16$，回流 $6$，变为 $22$。
3. 第 $3$ 位 $F_3=14$，当前 $22$，$14<22$，拨付 $2$，变为 $20$。

初始为 $0$ 时依次回流 $4,6,5$，答案为 $15$。

初始为 $20$ 时：先拨付 $2$ 得 $18$，再回流 $6$ 得 $24$，最后拨付 $2$ 得 $22$。

数据范围

• $1\le K\le 1\times 10^4$
• $1\le F_i,R_i,P_i\le 5\times 10^2$，且 $R_i\le F_i$
• $1\le T\le 100000$
• $0\le s_j\le 1000000000$
• 所有输入均为整数