Graunte

Fermierul Ion, cândva cunoscut pentru porumbul său de înaltă calitate, a intrat in faliment. Acum, el se mulțumește să crească roșii pe un câmp pătratic împărțit în $N \cdot N$ parcele. La început, câmpul era gol, dar de-a lungul timpului, Ion a efectuat mai multe plantări respectând o regulă specială, numită formula roșiilor gustoase:

• se alege un număr $v$
• se alege o porțiune a câmpului definită de colțul stânga-sus $(a, b)$ și colțul dreapta-jos $(c, d)$. Cu alte cuvinte, pentru orice $1 \leq i, j \leq N$, porțiunea câmpului conține parcela de pe linia $i$ și coloana $j$ dacă $a \leq i \leq c$ și $b \leq j \leq d$.
• în fiecare parcelă din porțiune se plantează un număr de roșii egal cu suma modulo $1 \ 789$ a numerelor mai mici decât $v$ care sunt coprime cu $v$.

Din cauza dificultăților financiare, fermierul trebuie să recolteze câteva roșii. Pentru a ușura procesul de recoltare, Ion va culege în întregime toate liniile de pe care culege cel puțin o roșie. El dorește să aleagă un număr maxim posibil de linii consecutive, astfel încât numărul total de roșii culese să nu depășească o anumită valoare $k$. Ajutați-l să afle, pentru mai multe valori posibile ale lui $k$, de pe care linii trebuie să culeagă roșiile.

Date de intrare

Prima linie conține trei numere întregi, despărțite prin câte un spațiu: $N$ (dimensiunea câmpului), $Q_1$ (numărul de plantări) și $Q_2$ (numărul de valori $k$).

Următoarele $Q_1$ linii conțin câte $5$ valori întregi, despărțite prin câte un spațiu: $a \ b \ c \ d \ v$, reprezentând o plantare efectuată conform formulei roșiilor gustoase.

Următoarele $Q_2$ linii conțin câte un număr întreg $k$, pentru care trebuie determinată cea mai lungă secvență de linii consecutive care conține cel mult $k$ roșii.

Date de ieșire

Se vor afișa $Q_2$ linii, fiecare conținând două numere $a \ b$, despărțite printr-un spațiu, unde $a$ și $b$ sunt capetele celei mai lungi secvențe de linii consecutive care conține cel mult $k$ roșii.

Dacă există mai multe secvențe de lungime maximă, se va alege cea mai de sus.

Dacă nicio secvență nu îndeplinește condiția, se va afișa −1 − 1.

Restricții și precizări

• $1 \leq N \leq 10^6$
• $1 \leq Q_1 \leq 10^5$
• $1 \leq Q_2 \leq 10$
• $1 \leq a, b, c, d \leq N$, pentru toate cele Q1 plantări de roșii
• $0 \leq v \leq 10^6$, pentru toate cele $Q_1$ plantări de roșii
• $0 \leq k \leq 10^{18}$, pentru toate cele $Q_2$ valori pe care le ia $k$
• Se garantează că numărul total de roșii de pe câmp nu va depăși $10^{18}$.
• Dupa efectuarea mai multor plantări, numărul de roșii aflate într-o parcelă poate să atingă și să depășească $1 \ 789$.
• Doua numere sunt coprime daca cel mai mare divizor comun al lor este $1$

Exemplul 1

graunte.in

2 3 4
1 1 1 2 91
1 2 2 2 12
1 1 2 2 24
216
210
3500
3400

graunte.out

2 2
-1 -1
1 2
1 1

Explicație

$N = 2$, deci câmpul are $2$ linii și $2$ coloane. Pentru prima plantare, $a = b = c = 1$, $d = 2$, $v = 91$. Suma numerelor coprime cu $91$ care sunt mai mici decât $91$ este $3 \ 276$. Prin urmare, în cele două parcele de pe prima linie se vor planta $3 \ 276$ mod $1 \ 789 = 1 \ 487$ roșii. În timpul celei de-a două plantări, în parcelele de pe a doua coloana se plantează $1 + 5 + 7 + 11 = 24$ roșii. În timpul celei de-a treia plantări, în toate parcelele se plantează $1 + 5 + 7 + 11 + 13 + 17 + 19 + 23 = 96$ roșii. Astfel, numerele finale de roșii din fiecare parcelă vor fi cele de mai jos:

Prima valoare pe care o ia $k$ este $216$. A doua linie este singura în care numărul de rosii este $\leq 216$, așadar a doua linie este singura care poate fi inclusă în secvența cerută, deci răspunsul este 2 2. A doua valoare pe care o ia $k$ este $210$. Pe nicio linie nu avem cel mult $\leq 210$ roșii, așadar nicio linie nu poate fi inclusă în secvența cerută, deci raspunsul este −1 −1.