complet

Se consideră un graf neorientat complet cu $N$ vârfuri etichetate de la $1$ la $N$. Asociem fiecărui vârf $i$ o valoare inițială $v_i$. Valorile din vârfuri se transformă începând cu un moment ințial $T_0=0$ din secundă în secundă după următoarea regulă: valoarea într-un vârf $k$ la secunda $T+1$ este egală cu suma valorilor aflate în toate celelalte vârfuri la secunda $T$.

Cerință

Cunoscând $N$ – numărul de vârfuri ale grafului precum și valorile inițiale din vârfurile grafului, să se răspundă la $Q$ întrebări date perechi de forma $(t, p)$ cu semnificația: “Dacă după $t$ secunde se consideră valorile din vârfuri ordonate crescător, care este valoarea de pe poziția $p$?”. Deoarece aceste valori pot fi foarte mari, acestea vor fi calculate modulo $40 \ 099$.

Date de intrare

Fișierul de intrare complet.in conține pe prima linie două numere naturale nenule separate printr-un spațiu: $N$ și $Q$. Pe a doua linie se găsesc $N$ numere naturale nenule separate prin câte un spațiu, reprezentând valorile aflate inițial în vârfurile grafului. Linia a treia conține exact $9$ numere naturale separate prin câte un spațiu $x \ y \ z \ t_1 \ t_2 \ t_3 \ p_1 \ p_2 \ p_3$ cu ajutorul cărora vor fi construite cele $Q$ întrebări. Primele trei întrebări sunt date de perechile $(t_1, p_1)$, $(t_2, p_2)$, $(t_3, p_3)$. Întrebarea $i$ (cu $i=4..Q$) va fi generată cu relațiile:

• $t_i = 1 + (t_{i-3} \cdot x + t_{i-2} \cdot y + t_{i-1} \cdot z)\ \%\ 10^{15}$
• $p_i = 1 + (p_{i-3} \cdot x + p_{i-2} \cdot y + p_{i-1} \cdot z)\ \%\ N$
• $x, y, z$ sunt numere naturale nenule fixate de cel mult $3$ cifre

Date de ieșire

Fișierului de ieșire complet.out va conține $Q$ linii, fiecare dintre acestea conținând un singur număr reprezentând răspunsul la întrebarea corespunzătoare din fișierul de intrare, modulo $40 \ 099$.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$
• Valorile inițiale din noduri sunt naturale nenule și mai mici sau egale cu $30 \ 000$
• $1 \leq p_i \leq n$ pentru fiecare întrebare
• $0 \leq t_i \leq 10^{15}$ pentru fiecare întrebare
• $3 \leq Q \leq 10^{6}$

Exemplu

complet.in

4 4
1 4 2 3
1 1 1 1 1 1 1 1 1

complet.out

6
6
6
204

Explicație

Întrebările vor fi:
$1 \ 1$
$1 \ 1$
$1 \ 1$
$4 \ 4$
În secunda $1$ valorile sunt: $9 \ 6 \ 8 \ 7$
După sortare, pe prima poziție este $6$.
În secunda $4$ valorile sunt: $201$, $204$, $202$, $203$
După sortare, pe a patra poziție este $204$.