Background

${\rm CYJian}$ came up with a very fun game...

Problem Description

${\rm CYJian}$ now gives you a sequence of length $N$. You may choose a number $x$, and then obtain a score. The larger the score, the better.

The score is computed as follows:

First, mark all numbers that are less than or equal to $x$. Then, your score is the sum of the squares of the lengths of every consecutive marked segment.

${\rm CYJian}$ thought this was too easy, the answer is obviously just the maximum value so he changed the score to be the original score divided by the number you chose.

${\rm CYJian}$ still thought this was too easy, so he requires that the number of segments obtained by your chosen number must be within the range $l$ to $r$.

${\rm CYJian}$ still thought this was too easy, so he added $T$ queries.

${\rm CYJian}$ still thought this was too easy, so he decided to enforce online queries.

Input Format

The first line contains two positive integers $n$, $T$.

The second line contains $n$ positive integers $Num_i$, representing the sequence given by ${\rm CYJian}$.

In the next $T$ lines, each line contains four positive integers $a$, $b$, $x$, $y$. You need to obtain the actual $l$ and $r$ as follows:

l = (a * lastans + x - 1) % n + 1;
r = (b * lastans + y - 1) % n + 1;
if (l > r) swap(l, r);

Here, ${\rm lastans}$ denotes the product of the maximum score (the original score) from the previous query and the $x$ that achieves this maximum score. In particular, for the first query we define ${\rm lastans}=0$.

Output Format

Output $T$ lines. Each line contains two positive integers, representing the maximum score (the original score) that can be obtained for this query and the $x$ that achieves this maximum score. In particular, if there is no solution, output "$-1\ -1$" (in this case, $lastans$ is $1$). If there are multiple solutions, output the one with the largest chosen number.

$CYJian$ wants to know whether you are guessing, so you also need to tell him $L$, $R$, and $lastans \bmod n$ for this query.

See the sample for details.

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

Hint

${\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$

All other input numbers are within the range of ${\rm int}$.

Translated by ChatGPT 5