Problem Description

In a certain company cafeteria, the menu is arranged in a $D$ day cycle. The dishes in the cafeteria are represented by integers. On day $i$, $i + D$, $i + 2D$, ..., dish $C_i$ is served.

There are $N$ employees, each with a preference for certain dishes. Employee $j$ likes dish $K_j$. Each employee will always eat their preferred dish on days when it is served. On days when a dish other than their preference is served, they will only use the cafeteria if their last visit was $L$ days ago. Note that this does not apply to their first visit (see below).

For each integer $1 \leq j \leq N$, answer the following question:

• Suppose employee $j$ first uses the cafeteria on day $F_j$ (they will use it on this day even if the dish is not their preference, and they cannot use it before this day even if their preferred dish was served). Determine the number of times employee $j$ will eat their preferred dish until they have used the cafeteria a total of $T_j$ times.

Input Format

The input is given from the standard input in the following format:

$D$ $L$ $N$ $C_1$ $C_2$ $\cdots$ $C_D$ $K_1$ $F_1$ $T_1$ $K_2$ $F_2$ $T_2$ $ : $ $K_N$ $F_N$ $T_N$

Output Format

Output $N$ lines. The $j$-th line should contain the number of times employee $j$ eats their preferred dish.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
0
3

Sample Input #2

3 1 3
1 1 1
2 1 3
1 2 3
1 3 3

Sample Output #2

0
3
3

Sample Input #3

10 4 4
4 4 4 3 1 1 5 2 2 1
2 5 2
2 9 10
2 3 3
2 7 13

Sample Output #3

1
5
1
6

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq D \leq 10^5$
• $1 \leq L \leq 10^9$
• $1 \leq C_i, K_j \leq 10^5$
• $1 \leq F_j \leq D$
• $1 \leq T_j \leq 10^9$
• All inputs are integers

Sample Explanation 1

The cafeteria menu repeats every 4 days: $\{2, 3, 1, 3\}$.
- Employee 1 prefers dish 1. They eat dish 3 on day 2 and can eat their preferred dish 1 on day 3. Thus, they eat their preferred dish once, so output 1.
- Employee 2 prefers dish 3. They eat dish 1 on day 3. They never eat their preferred dish, so output 0.
- Employee 3 prefers dish 3. They eat dish 3 on days 4, 6, and 8. Thus, they eat their preferred dish 3 times, so output 3.

Sample Explanation 2

The cafeteria menu is dish 1 every day.
- Employee 1 prefers dish 2. They eat dish 1 on days 1, 2, and 3. They never eat their preferred dish, so output 0.
- Employees 2 and 3 prefer dish 1 and eat it every day. Output 3.

见题面 Input 部分

见题面 Output 部分