题目描述

给一个长度为 $n$ 的非负整数序列 $A_1,A_2,...,A_n$。现有 $m$ 个询问，每次询问给出$l,r,p,k$ ，问满足$l<=i<=r$ 且$A_i mod p = k$ 的值 $i$ 的个数。

输入格式

第一行两个正整数 $n$ 和 $m$。

第二行 $n$ 个数，表示 $A_1,A_2,...,A_n$ 。 以下 $m$ 行，每行四个数分别表示 $l,r,p,k$ 。满足 $1\lel\ler\len$。

输出格式

对于每个询问，输出一行，表示可行值 $i$ 的个数。

5 2
1 5 2 3 7
1 3 2 1
2 5 3 0

2
1

数据规模与约定

$0< {n,m} \le10^5$ ，任意 $1 \le i \le n$ 满足 $A_i\le 10^4，0<p\le10^4，0\le k < p$ 。

题目来源

2011福建集训