Description

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]$.

Input Format

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 Format

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

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

Hint

[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.

Translated by ChatGPT 5