#2506. calc

题目描述

     给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问，每次询问给出l,r,p,k，问满足l<=i<=r且Ai mod p = k的值i的个数。

输入格式

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

     第二行n个数，表示A1,A2,…,An。

     以下m行，每行四个数分别表示l,r,p,k。满足1<=l<=r<=n。

输出格式

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

样例

样例输入

         5 2  

         1 5 2 3 7  

         1 3 2 1  

         2 5 3 0  

样例输出

         2  

        1   

数据范围与提示

数据范围：

     0<n,m<=10^5，任意1<=i<=n满足Ai<=10^4，0<p<=10^4，0<=k<p。