AT_abc156_f [ABC156F] Modularness

[problemUrl]: https://atcoder.jp/contests/abc156/tasks/abc156_f 長さ $ k $ の数列 $ d_0,d_1,...,d_{k\ -\ 1} $ があります。 以下のクエリ $ q $ 個を順に処理してください。 - $ i $ 番目のクエリは $ 3 $ つの整数 $ n_i,x_i,m_i $ からなる。 長さ $ n_i $ の数列 $ a_0,a_1,...,a_{n_i\ -\ 1} $ を、 \\\[ \\begin{aligned} a\_j = \\begin{cases} x\_i & ( j = 0 ) \\\\ a\_{j - 1} + d\_{(j - 1)~\\textrm{mod}~k} & ( 0 < j \\leq n\_i - 1 ) \\end{cases}\\end{aligned} \\\] と定める。 $ (a_j~\textrm{mod}~m_i)\

入力は以下の形式で標準入力から与えられる。 > $ k $ $ q $ $ d_0 $ $ d_1 $ $ ... $ $ d_{k\ -\ 1} $ $ n_1 $ $ x_1 $ $ m_1 $ $ n_2 $ $ x_2 $ $ m_2 $ $ : $ $ n_q $ $ x_q $ $ m_q $

$ q $ 行出力せよ。 $ i $ 行目には、$ i $ 番目のクエリに対する答えを出力せよ。

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ k,\ q\ \leq\ 5000 $ - $ 0\ \leq\ d_i\ \leq\ 10^9 $ - $ 2\ \leq\ n_i\ \leq\ 10^9 $ - $ 0\ \leq\ x_i\ \leq\ 10^9 $ - $ 2\ \leq\ m_i\ \leq\ 10^9 $ ### Sample Explanation 1 $ 1 $ つ目のクエリについて、問題文で示した数列 {$ a_j $} は $ 3,6,7,11,14 $ になります。 - $ (a_0~\textrm{mod}~2)\ >\ (a_1~\textrm{mod}~2) $ - $ (a_1~\textrm{mod}~2)\ \ (a_4~\textrm{mod}~2) $ であるため、このクエリに対する答えは $ 1 $ です。