Fişierul intrare/ieşire:	complet.in, complet.out	Sursă	Lot Vaslui 2014 Seniori Baraj 6
Autor	Adrian Panaete	Adăugată de	Marian Darius •dariusdarius
Timp execuţie pe test	0.45 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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

Cerinta

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

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 (t₁, p₁), (t₂, p₂), (t₃, p₃). Î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) 10¹⁵$

- $p_i = 1 + (p_i-3 * x + p_i-2 * y + p_i-1 * 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 40099.

Restricţii

• 2 ≤ N ≤ 100 000
• Valorile initiale din noduri sunt numere naturale si mai mici sau egale cu 30 000
• 1 ≤ p_i ≤ N
• 0 ≤ t_i ≤ 10¹⁵ pentru fiecare intrebare
• 3 ≤ Q ≤ 1 000 000

Exemplu

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.

Cum se trimit solutii?