M - Cafeteria Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

ある社員食堂では D 日周期でメニューが組まれています。この食堂の料理は整数で表され、今日を 1 日目として i 日目、i + D 日目、i + 2D 日目、…、には料理 C_i が提供されます。

N 人の社員はそれぞれ食事にこだわりがあり、社員 j は料理 K_j を好んでいます。各社員は、好みの料理が提供される日には必ず食堂を利用してその料理を食べます。それ以外の料理が提供される日には、前回の利用が L 日前である場合のみ食堂を利用します。ただし、初回の利用についてはこの限りではありません (後述)。

各整数 1 \leq j \leq N について、以下の問題に答えてください。

  • 社員 j が F_j 日目に初めて食堂を利用するとする (この日に限って料理が好みでなくても利用するものとし、またこれより前に好みの料理が提供されていても利用できないものとする)。社員 j が合計で T_j 回食堂を利用するまでに好みの料理を食べる回数を求めよ。

制約

  • 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
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

N 行出力せよ。j 行目には、社員 j が好みの料理を食べる回数を出力せよ。

入力例 1

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

出力例 1

1
0
3

食堂のメニューは、4 日周期で \{ 2, 3, 1, 3 \} が繰り返されています。

  • 社員 1 は、料理 1 が好みです。はじめに 2 日目に料理 3 を食べ、次に 3 日目は料理 1 を食べることができます。よって 1 回好みの料理を食べることができるので、1 を出力してください。
  • 社員 2 は、料理 3 が好みです。3 日目に料理 1 を食べます。好みの料理を一度も食べることができないので、0 を出力してください。
  • 社員 3 は、料理 3 が好みです。はじめに 4 日目に料理 3 を、6 日目に料理 3 を、8 日目に料理 3 を食べます。よって 3 を出力してください。

入力例 2

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

出力例 2

0
3
3

食堂のメニューは毎日 1 です。

  • 社員 1 は、料理 2 が好みです。はじめに 1 日目に料理 1 を食べた後、L = 1 であるので 2, 3 日目も料理 1 を食べます。好みの料理はメニューに含まれないので 0 を出力してください。
  • 社員 2, 3 は料理 1 が好きであり、毎日好みの料理を食べます。3 を出力してください。

入力例 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

出力例 3

1
5
1
6

Score : 6 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

The menu in some company cafeteria is based on a D-day cycle. Its dishes are represented by integers, and it serves Dish C_i on Day i, Day i + D, Day i + 2D, and so on, where today is Day 1.

The N employees who use this cafeteria are particular about food, and Employee j loves Dish K_j. Each employee always uses the cafeteria on a day when the favorite dish is served and gets it. On the other days, an employee uses the cafeteria only if the last day when he/she used it is L days ago. However, the above does not apply when it is the first time for him/her to use it (described below).

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

  • Assume that Employee j uses the cafeteria on Day F_j for the first time. (For this day only, he/she uses it even if the served dish is not his/her favorite. Also, assume that he/she cannot use the cafeteria before this day even when his/her favorite dish is served.) Find the number of times Employee j gets the favorite dish until he/she uses the cafeteria T_j times in total.

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 values in input are integers.

Input

Input is given from 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

Print N lines. The j-th line should contain the number of times Employee j gets the favorite dish.

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

The cafeteria serves the dishes with a 4-day cycle: \{ 2, 3, 1, 3 \}.

  • Employee 1 loves Dish 1. He first eats Dish 3 on Day 2, then eats Dish 1 on Day 3. Thus, he gets his favorite dish once, and we should print 1.
  • Employee 2 loves Dish 3. He eats Dish 1 on Day 3, and that is it. Thus, he gets his favorite dish zero times, and we should print 0.
  • Employee 3 loves Dish 3. He first eats Dish 3 on Day 4, then eats Dish 3 on Day 6, then eats Dish 3 on Day 8. Thus, we should print 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

The cafeteria serves Dish 1 every day.

  • Employee 1 loves Dish 2. He first eats Dish 1 on Day 1, then also eats Dish 1 on Day 2 and 3 since L = 1. The cafeteria never offers his favorite, so we should print 0.
  • Employee 2 and 3 love Dish 1, and they get their favorite every day, so we should print 3 for each of them.

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