Prove the Possibility of Humanity

In order to prove the possibility of humanity, you are given a sequence (a = [a_1,a_2,\cdots,a_n]) and need to answer (q) queries.

Each query is given as a tuple ((x, y)), a modulus (m) and an interval ([l, r]). For each query, count the number of indices (i) in the interval ([l, r]) that satisfy the condition:
[ (a_i + x) \bmod m < (a_i + y) \bmod m ]

It is guaranteed that the input is valid and the answer for each query should be printed on a new line.

inputFormat

The first line contains two integers (n) and (q) representing the number of elements in the sequence and the number of queries respectively.

The second line contains (n) integers (a_1, a_2, \dots, a_n) representing the sequence.

Each of the following (q) lines contains five integers: (x), (y), (m), (l), and (r), describing a query.

outputFormat

For each query, output a single integer on a new line representing the number of indices (i) in the interval ([l, r]) that satisfy the condition ((a_i + x) \bmod m < (a_i + y) \bmod m).

sample

5 3
1 2 3 4 5
1 2 5 1 5
2 1 5 2 4
3 4 5 3 5

4
1
3