余数序列

题目描述

有长度为 $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 \lt j \leq n_i - 1 ) \end{cases}\end{aligned}$$

输出满足 $(a_j~\textrm{mod}~m_i) \lt (a_{j + 1}~\textrm{mod}~m_i)$ 的 $j~(0 \leq j \lt n_i - 1)$ 的个数。

这里,对于两个整数 $y, z~(z \gt 0)$,$(y~\textrm{mod}~z)$ 表示 $y$ 除以 $z$ 的余数。

输入格式

输入按以下格式从标准输入给出:

$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

对于第 $1$ 个查询,问题中定义的数列 {$a_j$} 为 $3,6,7,11,14$。

• $(a_0~\textrm{mod}~2) \gt (a_1~\textrm{mod}~2)$
• $(a_1~\textrm{mod}~2) \lt (a_2~\textrm{mod}~2)$
• $(a_2~\textrm{mod}~2) = (a_3~\textrm{mod}~2)$
• $(a_3~\textrm{mod}~2) \gt (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

数据范围

• 输入均为整数
• $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$