AT_past202004_m 食堂

[problemUrl]: https://atcoder.jp/contests/past202004-open/tasks/past202004_m ある社員食堂では $ 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 $ 回食堂を利用するまでに好みの料理を食べる回数を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ が好みの料理を食べる回数を出力せよ。

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ - 入力は全て整数 ### Sample Explanation 1 食堂のメニューは、$ 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 $ を出力してください。 ### Sample Explanation 2 食堂のメニューは毎日 $ 1 $ です。 - 社員 $ 1 $ は、料理 $ 2 $ が好みです。はじめに $ 1 $ 日目に料理 $ 1 $ を食べた後、$ L\ =\ 1 $ であるので $ 2,\ 3 $ 日目も料理 $ 1 $ を食べます。好みの料理はメニューに含まれないので $ 0 $ を出力してください。 - 社員 $ 2,\ 3 $ は料理 $ 1 $ が好きであり、毎日好みの料理を食べます。$ 3 $ を出力してください。