complet

Complet

== include(page="template/taskheader" task_id="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ă $vi$. Valorile din vârfuri se transformă începând cu un moment inţial $T0=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$.

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

h2. Cerinta

h2. 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 t1 t2 t3 p1 p2 p3$ cu ajutorul cărora vor fi construite cele $Q$ întrebări. Primele trei întrebări sunt date de perechile $(t1, p1), (t2, p2), (t3, p3)$. Întrebarea $i$ (cu $i=4..Q$) va fi generată cu relaţiile:
- $ti = 1 + (ti-3 * x + ti-2 * y + ti-1 * z) % 10^15$
- $pi = 1 + (pi-3 * x + pi-2 * y + pi-1 * z) % N$

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 t1 t2 t3 p1 p2 p3$ 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~} * x + t{~i-2~} * y + t{~i-1~} * z) mod 10^15^$
- $p{~i~} = 1 + (p{~i-3~} * x + p{~i-2~} * y + p{~i-1~} * z) mod N$

- $x, y, z$ sunt numere naturale nenule fixate de cel mult $3$ cifre
h2. Date de ieşire

* $2 ≤ N ≤ 100 000$
* Valorile initiale din noduri sunt numere naturale si mai mici sau egale cu 30 000

* $1 ≤ pi ≤ N$
* $0 ≤ ti ≤ 10^15$ pentru fiecare intrebare

* $1 ≤ p{~i~} ≤ N$
* $0 ≤ t{~i~} ≤ 10^15^$ pentru fiecare intrebare

* $3 ≤ Q ≤ 1 000 000$
h2. Exemplu