F - 模块化

得分：600分

问题描述

我们有一个长度为$k$的数列：$d_0,d_1,...,d_{k-1}$。

按顺序处理以下$q$个查询：

• 第$i$个查询包含三个整数$n_i$，$x_i$和$m_i$。 设$a_0,a_1,...,a_{n_i-1}$是以下$n_i$个数字的序列：\[ \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) < (a_{j+1}~\textrm{mod}~m_i)$的$j$的个数（$0 \leq j < n_i-1$）。

这里$(y~\textrm{mod}~z)$表示$y$除以$z$的余数，其中$y$和$z$是整数且$z > 0$。

约束

• 输入中的所有值都是整数。
• $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$

输入

输入以以下格式从标准输入读入：

$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$次查询的回答。

3 1
3 1 4
5 3 2

1

对于第一个查询，序列{$a_j$}将变为$3,6,7,11,14$。

• $(a_0~\textrm{mod}~2) > (a_1~\textrm{mod}~2)$
• $(a_1~\textrm{mod}~2) < (a_2~\textrm{mod}~2)$
• $(a_2~\textrm{mod}~2) = (a_3~\textrm{mod}~2)$
• $(a_3~\textrm{mod}~2) > (a_4~\textrm{mod}~2)$

因此，对于这个查询的回答应该是$1$。

7 3
27 18 28 18 28 46 1000000000
1000000000 1 7
1000000000 2 10
1000000000 3 12

224489796
214285714
559523809