Fișierul intrare/ieșire	oof.in, oof.out	Sursă	Olimpiada pe școală 2019
Autor	Cella Florescu	Adăugată de	Cella Florescu • cella.florescu
Timp de execuție pe test	0.1 sec	Limită de memorie	5120 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

N sau 0 (clasa a 6-a)

Un grup de N prieteni s-a dus în timpul vacanței la munte, unde copiii au decis că se vor distra jucând jocul “N sau 0” (joc binecunoscut, unde se știe că vigilența, anduranța și non-agresivitatea primează). Fiind însă un grup numeros, au nevoie de un lider pentru o bună desfășurare. După multe sfătuiri și alegeri mai mult sau mai puțin democratice au stabilit următorul procedeu pentru a desemna șeful: se vor alinia toți într-un șir si vor fi numerotați de la stânga la dreapta cu numerele de la 1 la N și asupra acestui șir vor fi aplicate K eliminări succesive. La fiecare eliminare se alege arbitrar un număr natural X și se elimină copiii din X în X începând cu primul din șir, copiii eliminați părăsind definitiv selecția de lider spunând “oof”. Cu alte cuvinte, se elimină copiii de pe pozițiile 1, X + 1, 2X + 1, 3X + 1, ... până când poziția de pe care trebuie să eliminăm devine mai mare strict decât numărul de copii rămași în șir. După fiecare eliminare, șirul de copii se concatenează astfel încât să se ocupe noile poziții rămase goale și să se păstreze ordinea relativă. La finalul celor K eliminări, liderul va fi copilul aflat pe a P-a poziție în șirul rămas.

Cum dezbaterile febrile i-au epuizat însă pe toți cei N prieteni, la sfârșitul procedeului au constatat că au uitat tot ce s-a petrecut de-a lungul celor K eliminări, inclusiv numerele care le-au fost atribuite la început. Prin urmare, tu ești rugat să îi ajuți spunând ce număr avea liderul în șirul inițial (informație bineînțeles critică).

Date de intrare

Fișierul de intrare oof.in conține pe prima linie numerele naturale N, K și P, semnificând numărul de copii aflați inițial în șir, numărul de eliminări ce se vor face, respectiv poziția copilului din șirul final, căruia vrem să îi determinăm numărul. Următoarele K linii conțin fiecare câte un număr natural X care reprezintă modului respectivei eliminări.

Date de ieșire

În fișierul de ieșire oof.out se va scrie un singur număr, cel al copilului de pe a P-a poziție din șirul de copii rămași după K eliminări.

Restricții

• 1 ≤ N ≤ 1000000
• 0 ≤ K ≤ 100000
• 2 ≤ X ≤ 2³²-1 pentru fiecare eliminare.
• Se garantează că la finalul celor K eliminări rămân cel puțin P copii.

Exemplu

Explicație

Pentru primul exemplu:
Inițial șirul de copii este: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20.
După prima eliminare rămân copiii cu numerele: 2 3 5 6 8 9 11 12 14 15 17 18 20.
După a doua eliminare rămân copiii cu numerele: 3 6 9 12 15 18.
După ultima eliminare șirul de copii rămași este: 6 9 12 15 18, iar copilul de pe a 4-a poziție este cel cu numărul 15.

Pentru al doilea exemplu:
Inițial șirul de copii este: 1 2 3 4 5 6 7 8 9 10 11 12.
După prima eliminare rămân copiii cu numerele: 2 4 6 8 10 12.
După a doua eliminare rămân copiii cu numerele: 4 6 8 12, iar copilul de pe a 4-a poziție este cel cu numărul 12.