P9212 "Penglai Ningyou"

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.

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

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 $q$ lines in total. On the $i$-th line, output the answer to the $i$-th query.

### 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