Background

Mokou, who never grows old and never dies, can she still be called a "human"?

A human who has gone beyond life and death is unbelievable in itself.

Problem Description

To prove what humans are capable of, you need to solve a problem.

Given a sequence $a=[a_1,a_2,\cdots,a_n]$. There are $q$ queries:

• Each time you are given a pair $(x,y)$, a modulus $m$, and an interval $[l,r]$. Find how many $i\in [l,r]$ satisfy $(a_i+x)\bmod m<(a_i+y)\bmod m$.

Input Format

The first line contains two positive integers $n, q$, representing the length of the sequence and the number of queries.

The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$, describing the sequence $a$.

The next $q$ lines each contain five integers $l_i,r_i,x_i,y_i,m_i$, describing one query.

Output Format

Output $q$ lines in total. On the $i$-th line, output the answer to the $i$-th query.

10 5
4 3 2 5 8 5 3 3 1 2
1 10 3 7 6
4 10 5 5 4
2 7 1 2 9
5 9 3 4 7
1 3 5 1 8

4
0
6
3
2

Hint

Sample Explanation

• For the first query, the indices of elements that satisfy the condition are $1, 2, 7, 8$.
• For the second query, no element satisfies the condition.
• For the third query, the indices of elements that satisfy the condition are $2, 3, 4, 5, 6, 7$.
• For the fourth query, the indices of elements that satisfy the condition are $5, 6, 9$.
• For the fifth query, the indices of elements that satisfy the condition are $1, 2$.

Constraints and Notes

For all testdata, $1\le n\le 10^5$, $1\le q\le 5\times 10^5$, $1\le a_i,x_i,y_i,m_i\le 10^5$, $1\le l_i\le r_i\le n$.

Translated by ChatGPT 5