说明

岛村是不喜欢上课的。但是今天的数学课上，一个函数 $f(x)=\lfloor \frac{x+a}{b}\rfloor$ 吸引住了她。

她现在有一个长度为 $n$ 的序列 $A$ 和 $m$ 个询问。她想知道对于每组 $l,r,a,b$，记 $B_i=f(A_i)$，$\displaystyle\sum^r_{i=l+1}[B_i=B_{i-1}]$ 的值为多少（其中若 $[]$ 里面的表达式为真，值为 $1$，否则为 $0$）。

但是她着急于去找安达打乒乓球，所以把问题交给你了。

本题强制在线，每次的 $l,r,a,b$ 均要异或上一次的答案，若这是第一次询问，则不做操作。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $A_i$。

接下来 $m$ 行，每行四个整数 $l,r,a,b$。

输出格式

对于每次询问，输出一个整数表示答案。

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

4
1
1
3
2
2
1
0
4
1

提示

对于所有测试数据，保证：$1 \le n,m,A_i \le 10^5$，$1\le b\le 500$，$0 \le a\le2\times10^9$，$l<r$。