水の数列

${\rm CYJian}$想到了一个很好玩的游戏呢...

${\rm CYJian}$现在给你一个长度为$N$的数列，你可以选择一个数$x$，然后获得一个得分，得分越大越好。 得分是这样计算的: 首先把小于等于$x$的数标记，然后你的得分就是每一个连续标记的区间的长度的平方和。 ${\rm CYJian}$觉得这样太简单了，~~答案显然就是最大值嘛~~所以他就把得分改成了原来的得分除以你选择的数。 ${\rm CYJian}$还是觉得这样太简单了，所以他需要你选择的数得到的区间的个数在$l$~$r$的范围内。 ${\rm CYJian}$还是觉得这样太简单了，所以他加上了$T$组询问。 ${\rm CYJian}$还是觉得这样太简单了，所以他决定强制在线。

第一行两个正整数$n$，$T$。 第二行$n$个正整数$Num_i$表示${\rm CYJian}$给出的数列。 接下来$T$行，每行四个正整数$a$，$b$，$x$，$y$，你需要这样得到真正的$l$和$r$: ``` l = (a * lastans + x - 1) % n + 1; r = (b * lastans + y - 1) % n + 1; if (l > r) swap(l, r); ``` 其中${\rm lastans}$表示上一次询问的最大分数(原始得分)和得到这个最大的分数的$x$的乘积。特别的，我们令第一次询问时${\rm lastans}=0$。

$T$行，每行两个正整数表示每一次询问能得到的最大的分数(原始的得分)和得到这个最大的分数的$x$。特别的，如果无解输出"$-1\ -1$"（此时 $lastans$ 为 $1$）。如果有多解则输出选择的数最大的一组。 $CYJian$想知道你是不是蒙的，所以你还需要告诉他**这一次询问的**$L$，$R$，$lastans \bmod n$。 具体参见样例。

5 3
3 5 1 2 4
233 666 1 3
555 999 2 3
123 987 233 888

25 5
1 3 0
10 4
2 3 0
-1 -1
3 3 0

${\rm Subtask\ 1(30\ pts)}:\qquad 1 \leq N,T \leq 10^2$ ${\rm Subtask\ 2(30\ pts)}:\qquad 1 \leq N,T \leq 10^3$ ${\rm Subtask\ 3(40\ pts)}:\qquad 1 \leq N \leq 10^6 \qquad 1 \leq T \leq 10^3$ $1 \leq Num_i \leq 10^6$ 其余输入的数字均在${\rm int}$范围内。