P5012 Water Sequence

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

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

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 $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.

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