În curtea școlii, N copii stau așezați în cerc; pe tricouri sunt scrise, în ordine, numerele de la 1 la N și fiecare copil ține în mână un cartonaș cu un număr natural nenul.

Ei decid să joace un joc de echipă care necesită multă răbdare. Regula jocului este următoarea:

• la fiecare pas:
  • se alege copilul care are cel mai mic număr scris pe cartonaș; dacă sunt mai mulți copii cu același număr minim, va fi ales copilul care are pe tricou un număr mai mic.
  • copilul ales trebuie să adune la valoarea curentă de pe cartonașul său valoarea pe care a avut-o la începutul jocului.
• jocul se termină atunci când toți copiii au pe cartonașe aceeași valoare.

De exemplu, dacă sunt N = 3 copii având pe cartonașe numerele 6 3 4, jocul se va desfășura în felul următor:

Numerele de pe cele trei cartonașe sunt egale; jocul s-a încheiat după 6 pași, iar valoarea finală de pe toate cartonașele este 12.

Cerința

Cunoscând numărul de copii N și numerele inițiale de pe cartonașe, scrieți un program care să determine:

• Care este valoarea finală la care vor ajunge toți copiii la finalul jocului?
• Care este numărul total de pași efectuați până la finalul jocului?
• Pentru un număr K dat, care este copilul ales la pasul K?

Date de intrare

Fișierul de intrare joc.in conține pe prima linie numărul natural C, care poate fi doar 1, 2 sau 3 și reprezintă cerința care trebuie rezolvată.
Pe linia a doua se află numărul N, iar pe a treia linie se află cele N numere de pe cartonașe, în ordinea numerelor de pe tricou.
Dacă C = 3, pe a patra linie se află numărul K.

Date de ieșire

Fișierul de ieșire joc.out va conține:

• dacă C = 1, un număr natural reprezentând valoarea finală la care vor ajunge copii;
• dacă C = 2, un număr natural reprezentând numărul total de pași efectuați;
• dacă C = 3, un număr natural reprezentând numărul scris pe tricoul copilului care efectuează pasul K.

Restricții și precizări

Pentru C = 1 și C = 2

• 1 ≤ N ≤ 1000;
• numerele de cartonașe sunt mai mici decât 2.000.000.000;
• valoarea finală comuna pentru toți copii va fi mai mică decât 2.000.000.000;
• pentru jumătate din punctaj, 1 ≤ N ≤ 100 și numărul total de pași efectuați pentru a încheia jocul este mai mic decât 50.000.

Pentru C = 3

• 1 ≤ N ≤ 100;
• 1 ≤ K ≤ 50.000;
• numerele de cartonașe sunt mai mici decât 1.000
• valoarea finală comuna pentru toți copii va fi mai mică decât 2.000.000.000
• numărul total de pași efectuați pentru a încheia jocul este mai mic decât 50.000

Pentru 20 de puncte, C=1. Pentru 30 de puncte, C=2. Pentru 50 de puncte, C=3.

Exemplul 1

joc.in

1
3
6 3 4

joc.out

12

Explicație

Se rezolvă prima cerință. Valoarea finală comună este 12.

Exemplul 2

joc.in

2
3
6 3 4

joc.out

6

Explicație

Se rezolvă a doua cerință. Jocul se termină după 6 pași.

Exemplul 3

joc.in

3
3
6 3 4
5

joc.out

3

Explicație

Se rezolvă a treia cerință. Al 5-lea pas este efectuat de copilul care are pe tricou numărul 3.