calc

给定一个长度为 $n$ 的非负整数序列 $A_1,A_2,\ldots,A_n$。

现有 $m$ 次询问，每次询问给出 $l,r,p,k$，求满足 $l\le i\le r$ 且 $A_i\bmod p=k$ 的下标 $i$ 的数量。

输入格式

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

第二行包含 $n$ 个非负整数，依次表示 $A_1,A_2,\ldots,A_n$。

接下来 $m$ 行，每行包含四个整数 $l,r,p,k$，表示一次询问。保证 $1\le l\le r\le n$。

输出格式

对于每次询问，输出一行一个整数，表示满足条件的下标 $i$ 的数量。

样例输入

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

样例输出

2
1

数据范围

• $0<n,m\le 10^5$；
• 对任意 $1\le i\le n$，满足 $A_i\le 10^4$；
• $0<p\le 10^4$；
• $0\le k<p$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

2
1