分数: 433 分
问题陈述
高桥制定了一个管理计划,该计划每隔 N 天。在此计划中,每天确定收入、采购成本和人工成本。
当天 管理计划 i (1 \leq i \leq N) ,当日结束,资金增加 A_i - B_i - C_i 日元,其中 A_i 代表收入, B_i 代表采购成本,并且 C_i 代表人工成本。 (如果增加为负数,则资金减少。)
本管理计划返回日 1 日复一日 N,并且相同的计划无限重复。
如果在任何一天结束时资金少于 0 日元(负),该公司被认为已经走了 破产 给出了.
Q 查询。在 j第查询,高桥从当天开始管理 管理计划的 L_j ,他的资金是 S_j 日前一点的日元 L_j的处理发生。
此后,每天按照管理计划的顺序进行管理。即管理计划中的天数按顺序进行 L_j, L_j+1, \ldots, N, 1, 2, \ldots。进行管理的第一天(day 管理计划的 L_j )被算作“管理开始后的第1天”。
对于每个查询,输出自管理开始以来公司第一次破产的日期(当天结束时)。如果公司永远不会破产,无论管理持续多久,产出 0.
约束
- 1 \leq N
- 1 \leq Q
- N + Q \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 0 \leq B_i \leq 10^9
- 0 \leq C_i \leq 10^9
- 1 \leq L_j \leq N
- 0 \leq S_j \leq 10^{12}
- 所有输入均为整数
输入
N Q A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N L_1 S_1 L_2 S_2 \vdots L_Q S_Q
- 第一行包含一个整数 N 表示管理计划周期的天数和整数 Q 代表查询数量,以空格分隔。
- 以下 N 行提供有关管理计划每一天的信息。
- 的 (1 + i)第行 (1 \leq i \leq N) 包含 A_i 代表当天的收入 i, B_i 代表采购成本,以及 C_i 代表人工成本,用空格分隔。
- 以下 Q 行提供有关每个查询的信息。
- 的 (1 + N + j)第行 (1 \leq j \leq Q) 包含 L_j 代表管理开始日 j第一个查询和 S_j 代表初始资金,以空格分隔。
输出
输出 Q 行。
关于 j第行,输出一个整数,代表自管理开始以来公司第一次破产的日期(当天结束时) j第一个查询。如果公司没有破产,输出 0.
示例输入 1
3 5 10 3 2 4 7 5 8 4 3 1 0 1 10 2 7 3 1 2 20
示例输出 1
2 14 1 3 22
示例输入 2
4 4 5 2 3 10 4 1 0 0 0 7 3 2 1 0 2 1 3 100 4 5
示例输出 2
0 0 0 0
示例输入 3
8 8 100 30 20 20 50 10 0 40 30 80 20 20 10 5 5 50 60 20 200 100 50 30 20 40 1 0 2 25 3 100 4 10 5 60 6 5 7 1000 8 15
示例输出 3
3 1 17 8 7 1 269 1
示例输入 4
20 15 1000000000 400000000 300000000 200000000 500000000 100000000 0 600000000 500000000 750000000 250000000 250000000 123456789 123456789 0 900000000 100000000 100000000 10000000 20000000 30000000 500000000 600000000 100000000 1000000000 0 0 0 0 0 300000000 100000000 250000000 800000000 900000000 50000000 450000000 200000000 100000000 100000000 300000000 400000000 600000000 100000000 100000000 700000000 350000000 350000000 1 1000000000 0 999999999 1 1 250000000 250000000 250000000 400000000 100000000 200000000 1 0 1 1000000000000 3 500000000 5 123456789 7 10000000 9 0 10 100 12 800000000 14 1500000000 16 0 18 999999999999 20 300000000 4 700000000 11 250000000 15 50
示例输出 4
2 0 1 19 1 9 2 6 10 2 0 4 0 4 3
示例输入 5
1 5 0 1000000000 1000000000 1 0 1 1 1 1999999999 1 2000000000 1 1000000000000
示例输出 5
1 1 1 2 501