题目背景

${\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}$范围内。