#2097. 「CQOI2015」任务查询系统

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。

超级计算机中的任务用三元组 (S_i,E_i,P_i) 描述, (S_i,E_i,P_i) 表示任务从第 S_i 秒开始,在第 E_i 秒后结束(第 S_i 秒和 E_i 秒任务也在运行),其优先级为 P_i 。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第 X_i 秒正在运行的任务中,优先级最小的 K_i 个任务(即将任务按照优先级从小到大排序后取前 K_i 个)的优先级之和是多少。特别的,如果 K_i 大于第 X_i 秒正在运行的任务总数,则直接回答第 X_i 秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在 1 n 之间(包含 1 n )。

输入格式

输入文件第一行包含两个空格分开的正整数 m n ,分别表示任务总数和时间范围。

接下来 m 行,每行包含三个空格分开的正整数 S_i E_i P_i (S_i \leq E_i) ,描述一个任务。

接下来 n 行,每行包含四个空格分开的整数 X_i A_i B_i C_i ,描述一次查询。查询的参数 K_i 需要由公式 K_i=1+(A_i \cdot \text{Pre}+B_i) \mod C_i 计算得到。其中 \text{Pre} 表示上一次查询的结果,对于第一次查询, \text{Pre}=1

输出格式

输出共 n 行,每行一个整数,表示查询结果。

样例

样例输入

4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3

样例输出

2
8
11

样例解释

K_1 = (1 \times 1+3) \mod 2+1 = 1

K_2 = (1 \times 2+3) \mod 4+1 = 2

K_3 = (2 \times 8+4) \mod 3+1 = 3

数据范围与提示

对于 100 \% 的数据, 1 \leq m,n,S_i,E_i,C_i \leq 100000, \ 0 \leq A_i,B_i \leq 100000, \ 1 \leq P_i \leq10000000 X_i 1 n 的一个排列。