The laboratory is currently developing a task management system for its supercomputer, and you have been assigned to implement the query component.

Tasks in the supercomputer are described by triples $(S_i, E_i, P_i)$, where $(S_i, E_i, P_i)$ indicates that a task starts at second $S_i$ and ends after second $E_i$ (the task is also running during seconds $S_i$ and $E_i$), with a priority of $P_i$. Multiple tasks may run simultaneously, and they may have the same or different priorities.

The scheduling system frequently queries the query system for the sum of the priorities of the $K_i$ tasks with the smallest priorities among those running at second $X_i$ (i.e., sort the tasks running at second $X_i$ by priority in ascending order and take the first $K_i$ tasks). Specifically, if $K_i$ is greater than the total number of tasks running at second $X_i$, return the sum of the priorities of all tasks running at second $X_i$. All parameters mentioned above are integers, and the time range is from $1$ to $n$ (inclusive).

Input

The first line of the input contains two space-separated positive integers $m$ and $n$, representing the total number of tasks and the time range, respectively.

The next $m$ lines each contain three space-separated positive integers $S_i$, $E_i$, and $P_i$ ($S_i \le E_i$), describing a task.

The next $n$ lines each contain four space-separated integers $X_i$, $A_i$, $B_i$, and $C_i$, describing a query. The query parameter $K_i$ must be calculated using the formula $K_i = 1 + (A_i \times \text{Pre} + B_i) \pmod{C_i}$, where $\text{Pre}$ represents the result of the previous query. For the first query, $\text{Pre} = 1$.

Output

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

Examples

Input 1

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

Output 1

2
8
11

Note

$K_1 = (1 \times 1 + 3) \pmod 2 + 1 = 1$ $K_2 = (1 \times 2 + 3) \pmod 4 + 1 = 2$ $K_3 = (2 \times 8 + 4) \pmod 3 + 1 = 3$

Constraints

• For 50% of the data, $A_i = 0$.
• For 100% of the data, $1 \le m, n, S_i, E_i, C_i \le 100\,000$, $0 \le A_i, B_i \le 100\,000$, $1 \le P_i \le 10\,000\,000$, and $X_i$ is a permutation of $1$ to $n$.