题目描述

街上的街灯亮起，指引向着远方的路。每个街灯上都有一个数，每次询问，
第l个街灯到第r个街灯上的数模p等于v的有几个。

输入

第一行两个数N,M，代表街灯的个数和询问的个数。
一行N个数，代表街灯上的数。
接下来M行，每行四个数l,r,p,v代表一组询问。

输出

对于每次询问，输出一行代表答案。

输入样例

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

输出样例

2
1

限制

时间:1500ms
空间:256MB

数据范围

对于30%的数据，1≤N,M≤10^3;
另外对于30%的数据，每次询问的p一样;
对于100%的数据，1≤N,M≤10^5 ，街灯上的数不超过10^4，1≤p≤10^9 。

p.s.

from 高天宇
Manual input by autihero（微笑）