3932 - [CQOI2015]任务查询系统

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(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≤E_i)，描述一个任务。

接下来n行，每行包含四个整数X_i,A_i,B_i,C_i描述一次查询。查询的参数K_i需要由公式 K_i＝1＋(A_i×Pre＋B_i) \pmod {C_i}计算得到。其中Pre表示上一次查询的结果，对于第一次查询，Pre＝1。

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

K_1＝(1×1＋3)\mod 2＋1＝1,K_2＝(1×2＋3)\mod4＋1＝2,K_3＝(2×8＋4)\mod3＋1＝3

对于100\%的数据，1≤m,n,S_i,E_i,C_i≤10^5，0≤A_i,B_i≤10^5,1≤P_i≤10^7，X_i为1到n的一个排列。