Island Village's Floor Function Queries

Island Village isn’t fond of attending class. However, during today’s mathematics lesson, she became intrigued by the function \(f(x)=\lfloor\frac{x+a}{b}\rfloor\).

You are given an array \(A\) of length \(n\) and \(m\) online queries. In each query, you are given four integers \(l, r, a, b\). First, define \(B_i=f(A_i)=\lfloor\frac{A_i+a}{b}\rfloor\) for \(1\le i\le n\). You then need to compute the sum

[ \sum_{i=l+1}^{r} [B_i=B_{i-1}], ]

where the expression \([B_i=B_{i-1}]\) equals \(1\) if \(B_i=B_{i-1}\) and \(0\) otherwise.

Online Query Twist: This is an online problem. For every query except the first one, each of the four integers \(l, r, a, b\) is XORed with the answer of the previous query. That is, if \(lastAns\) is the output for the previous query, then the actual parameters for the current query become:

[ \begin{aligned} \tilde{l} &= l\oplus lastAns,\ \tilde{r} &= r\oplus lastAns,\ \tilde{a} &= a\oplus lastAns,\ \tilde{b} &= b\oplus lastAns. \end{aligned} ]

It is guaranteed that after the XOR operations, the indices \(l\) and \(r\) define a valid segment (with \(1\le l\le r\le n\)) and \(b\) is nonzero.

Your task is to process \(m\) queries and output the answer for each query.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 10^5)\).

The second line contains \(n\) integers, representing the array \(A\).

Then \(m\) lines follow, each containing four integers \(l, r, a, b\). For the first query, these are the actual parameters; for subsequent queries, each parameter is XORed with the previous query's answer.

outputFormat

For each query, output a line containing a single integer — the computed sum \(\sum_{i=l+1}^{r}[B_i=B_{i-1}]\).

sample

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

1
1
1