分数: 400 分
问题陈述
有一条走廊,包括 L 房间水平排列。房间编号从 0 to L - 1 从左到右。
每对相邻的房间之间有一扇门。具体来说,对于每个整数 x 满意 1 \leq x \leq L - 1,有门 x 房间之间 x - 1 和房间 x。走廊两端(房间左侧 0 和房间的右侧 L-1) 是外墙,不能穿过。
这条走廊有 N 配置的安全模式类型。安全图案 i 有模数 A_i,初始值 R_i和时间系数 V_i。在整数时间 t,如果门 x (1 \leq x \leq L - 1) 满足
x \equiv R_i + V_i \cdot t \pmod{A_i}
然后安全模式 i 地方 1 锁上那扇门。多种安全模式可以同时在同一扇门上上锁。
的 重量 门 x 时间 t 定义为当时该门上的锁总数 t.
你被给予 Q 查询。查询中 j,高桥在房间里 S_j 时间 T_j。及时修复锁的状态 T_j (不考虑随时间的变化)并考虑以下事项。
高桥的体力是 P_j。让高桥到达房间 c 来自房间 S_j,他必须穿过之间的所有门 S_j 和 c 按顺序。如果他经过的门的总重量最多为 P_j,然后高桥就可以到达房间 c.
对于每个查询,查找 Takahashi 可以到达的房间数量。注意那个房间 高桥开始的 S_j 也算作可达房间。
约束
- 1 \leq N \leq 10^5
- 2 \leq L \leq 10^9
- 1 \leq Q \leq 10^5
- N \times Q \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- 0 \leq R_i \leq A_i - 1
- 0 \leq V_i \leq A_i - 1
- 0 \leq T_j \leq 10^9
- 0 \leq S_j \leq L - 1
- 0 \leq P_j \leq 10^{14}
- 所有输入均为整数。
输入
N L Q A_1 R_1 V_1 A_2 R_2 V_2 : A_N R_N V_N T_1 S_1 P_1 T_2 S_2 P_2 : T_Q S_Q P_Q
- 第一行包含 N 代表安全图案的数量, L 代表房间数量,以及 Q 代表查询数量,以空格分隔。
- 以下 N 行给出安全模式信息。
- 的 (1 + i)第行包含模数 图案的 A_i,初始值 R_i和时间系数 V_i 图案的 i,用空格分隔。
- 以下 Q 行给出查询信息。
- 的 (1 + N + j)- 第行包含时间 T_j,房间号 S_j 高桥在哪里,以及体力 P_j 查询 j,用空格分隔。
输出
输出 Q 行。
关于 j第行,输出高桥可到达的房间数以供查询 j.
示例输入 1
2 6 4 2 0 1 3 1 0 0 0 0 0 2 2 1 3 1 2 5 10
示例输出 1
1 6 4 6
示例输入 2
3 8 5 4 1 1 5 0 2 2 1 0 0 4 3 1 0 1 2 7 4 3 3 0 10 6 100
示例输出 2
7 2 5 1 8
示例输入 3
8 50 10 7 0 3 11 5 2 13 12 0 6 4 5 17 8 9 10 1 7 9 3 3 25 24 1 0 0 5 1 10 12 2 20 0 5 25 30 10 49 100 12345 17 50 999999 33 7 42 4 20 7 48 1 100 12 1000
示例输出 3
8 27 5 50 50 50 19 30 8 50
示例输入 4
20 100000 15 1000 0 1 99991 12345 67890 2 1 1 3 2 0 97 96 13 1000000000 999999999 0 50000 25000 24999 65536 32768 12345 12345 6789 1111 88888 77777 66666 100 0 99 999 998 997 100000 54321 1234 271828 1828 271 314159 26535 89793 42 17 23 73 0 72 1000000000 0 999999999 1234567 765432 123456 987654321 123456789 98765432 0 0 0 1 99999 10 2 50000 1000 1000 12345 50000 999999999 54321 100000000000000 314159265 999 123456789 271828182 88888 9876543210 42 4242 42 73 7300 7300 1000000000 1 1 555555555 77777 333333 123456789 23456 1000000 987654321 65432 999999999999 80808080 90909 12345678901234 60606060 10101 0
示例输出 4
1 11 2238 68321 100000 100000 100000 96 15474 2 100000 100000 100000 100000 2
示例输入 5
1 2 5 1 0 0 0 0 0 0 0 1 1000000000 1 0 1000000000 1 100000000000000 123 0 100000000000000
示例输出 5
1 2 1 2 2