题目描述

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

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

第$i$个查询包含三个整数$n_i,x_i,m_i$。

$$a_j= \begin{cases} x& j=0 \\ a_{j-1}+d_{(j-1)\mod k}&0<j\leq n-1 \end{cases}$$

对于每组询问，请回答有多少个 $j$ 满足 $0\leq j< n-1$ 且 $(a_j\mod m_i)<(a_{j+1}\mod m_i)$。

输入

第一行两个整数$k,q$

第二行一个长度为$k$的序列

接下来一共$q$行，表示一组询问$n_i,x_i,m_i$

输出

输出$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

提示

• $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$