P3168 [CQOI2015] Task Query System

The laboratory is building a task management system for its supercomputer, and you are assigned to implement the query component. Each task in the supercomputer is described by a triple $(s_i, e_i, p_i)$, meaning it runs from second $s_i$ through second $e_i$ inclusive (the task is running at both second $s_i$ and second $e_i$), and its priority is $p_i$. Multiple tasks may run at the same time, and their priorities may be the same or different. The scheduler frequently asks the query system: among the tasks running at second $x_i$, what is the sum of priorities of the smallest $k_i$ tasks (i.e., sort tasks by priority in ascending order and take the first $k_i$)? In particular, if $k_i$ is larger than the number of tasks running at second $x_i$, return the sum of priorities of all tasks running at second $x_i$. All parameters are integers, and the time range is within $[1, n]$.

The first line contains two space-separated positive integers $m$ and $n$, the number of tasks and the time range, respectively. The next $m$ lines each contain three space-separated positive integers $s_i, e_i, p_i$ ($s_i \le e_i$), describing one task. The next $n$ lines each contain four space-separated integers $x_i, a_i, b_i, c_i$, describing one query. This problem is online. The parameter $k_i$ is computed by $k_i = 1 + (a_i \times \text{pre} + b_i) \bmod c_i$, where $\text{pre}$ denotes the previous query’s result, with initial $\text{pre} = 1$.

Output $n$ lines, each containing one integer, the result of each query.

[Sample explanation] $k_1 = (1\times 1 + 3)\bmod 2 + 1 = 1$. $k_2 = (1\times 2+3)\bmod 4 + 1 = 2$. $k_3 = (2 \times 8+4)\bmod 3+1 = 3$. Constraints For $100\%$ of the testdata, $1 \le m, n, c_i \le 10^5$, $0 \le a_i, b_i \le 10^5$, $1 \le s_i \le e_i \le n$, $1 \le p_i \le 10^7$, and the $x_i$ form a permutation of $1$ to $n$. Note: On 2024-12-28 a hack testdata was added, [post link](https://www.luogu.com.cn/discuss/1025247). Translated by ChatGPT 5