本题中规定插入排序一定是按照下面这段代码这样实现的：

for(i=2;i<=N;i++) {
    t=a[i];
    for(j=i-1;j>=1&&a[j]>t;j--)
        a[j+1]=a[j];
    a[j+1]=t;
}

插入排序时，序列可以看作两部分——已排序部分和未排序部分。显然一开始时已排序部分长度为1，然后每一轮长度都会增加1。

给你一个长度为n个序列，用插入排序算法对它进行排序。为了确保你不是用其他算法对它进行排序，你要回答m次提问，每次提问都是这样的格式：当已排序部分长度为k时，序列的第l个数到第r个数中有多少个数比x小（小于等于）。为了防止离线算法，题目会采取措施强制在线。

第一行五个正整数n,m,A,B,C，分别为序列长度，提问次数，和三个参数。

第二行n个正整数，表示原序列。

接下来m行，每行四个正整数k',l',r',x'。本次提问实际上是k=(k'+lastans)%n+1, l=(l'+lastans)%n+1, r=(r'+lastans)%n+1, x=(x'+A*lastans+B)%C。（如果l<r就交换l和r的值，另外注意x的生成方式与m,l,r不同）。设一开始lastans=0。

每次提问，输出一行，表示答案。

样例解释：

• 第一次提问实际上是1 1 3 3，这时的序列是4 3 2 1，答案是2。
• 第二次提问实际上是3 1 3 3，这时的序列是2 3 4 1，答案是2。
• 第三次提问实际上是3 1 2 0，这时的序列是2 3 4 1，答案是1。

数据范围：

2<=n,m<=1000000 1<=序列每个数<=10⁹ 1<=A,B,C<=10⁹