Description

街上的街灯亮起，指引向着远方的路。每个街灯上都有一个数，每次询问，第𝑙个街灯到第𝑟个街灯上的数模𝑝等于𝑣的有几个。

Format

Input

第一行两个数𝑁, 𝑀，代表街灯的个数和询问的个数。

接下来一行𝑁个数，代表街灯上的数。

接下来𝑀行，每行四个数𝑙, 𝑟, 𝑝, 𝑣代表一组询问。

Output

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

Samples

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

2
1

Range

对于30%的数据，1 ≤ 𝑁, 𝑀 ≤ 10$^3$。

对于另外30%的数据，每次询问的𝑝一样。

对于100%的数据，1 ≤ 𝑁, 𝑀 ≤ 10$^5$，街灯上的数不超过10$^4$，1 ≤ 𝑝 ≤ 10$^9$。

Limitation

1.5s, 256M for each test case.