Nash mali Draganče se našao u nevolji. Pre par nedelja se dogovorio sa drugarima da na leto ide na more u Abenishbe, ali je ubrzo shvatio da nema dovoljno para. Pa je odlučio da se zaposli i da zaradi te pare. Pošto ga niko nije shvatio ozbiljno da sa 10 godina ume da programira, morao je da se zaposli na nekom mnogo manje zanimljivom mestu - u prodavnici nakita. U toj prodavnici imaju jako veliki izbor - ogrlice, minđušhe, narukvice, prstenje... Našem malom Dragančetu za oko su posebno zapale ogrlice od perli. Perle su poređane u krug, i sa nekih perli iz kruga visi još po jedna niska perli. Svake dve susedne perle su povezane malim konchićem (i sa kruga i sa niski). Draganče je primetio da je ogrlica jako uska, tako da retko koja mušterija može da je stavi oko vrata, tako da i oni kojima se svidi, odustanu posle probavanja. Draganče je smislio kako da reši problem! Makazama će preseći jedan končić (koji spaja dve perle sa kruga), i neke dve perle će da spoji konchićem. Tako će da dobije ogrlicu istog tipa - krug sa visećim niskama perli. Poshto već par nedelja nije ništa programirao, jer svaki dan sedi u prodavnici, zamolio vas je da mu pomognete, i izračunate koliki najveći krug na ogrlici može da dobije, sa jednim sečenjem i jednim spajanjem. Naravno, kada bi znao najveći krug, mogao bi svakoj ogrlici da poveća krug, i samim tim poveća broj mušterija.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza)U prvom redu ulazne datoteke se nalazi broj n(n≤ 500000) koji predstavlja broj perli na krugu. Usledećem redu su dva broja, k i m (k≤ 10000,m≤ 10000000). U sledećih k redova se nalazi pojedan ceo broj niza x_i (x_i≤ 2*m). Niz a_iizračunajte koristeći doele navedeni segment programa (nizx_i ima k elemenata i njhovi indeksi su od 0 do k-1, aa_i ima n elemenata i njihovi indeksi su od 0 do n-1):

j = 0;
for (i = 0; i < n; i++) f a[i] = x[j];
 s = (j+1) % k;
 x[j] = ((x[j] ^ x[s]) + 13) % m;
 j = s;
}

(% označava ostatak po modulu, a ^ označava bitovski xor)Za Pascal programere bi segment imao sledeći izgled:

j := 0;
for i := 0 to n-1 do begin
 a[i] := x[j];
 s := (j+1) mod k;
 x[j] := ((x[j] xor x[s]) + 13) mod m;
 j := s;
end;

U ovom kodu je xor oznaka za bitovnu eksluzivnu disjunkcijukoja postoji kao operacija u Rascal-u.Broj a_i predstavlja broj perli u niski ispod i-te perle nakrugu. Rešenje ne zavisi od gornje formule, u njoj ne postojezavisnosti koje bi vam pomogle u rešavanju. Ona služi da ulaznadatoteka ne bude prevelika, da bi mogla da se učita u vremenskomograničenju.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvi red izlazne datoteke ispisati jedan ceobroj - broj perli u najvećem krugu koji se može dobitijednim sečenjem i jednim spajanjem dve perle date ogrlice.

Ogranicenja:

• Maksimalno vreme izvršavanja programa je 1.5 sekunda.

Primer 1:

12
12 5
3
0
3
2
2
0
2
0
1
0
1
0

17

Objašnjenje:

Ogrlica je prikazana na slici ispod odgovora. Nizovi x i a su identični.Ako presečemo između 2. i 3. perle sa kruga, i spojimo poslednje perle iz niski ispod 2. i3. perle, dobijamo dužinu 12 + 3 + 2 = 17.

Primer 2:

8
4 9
3
4
0
5

20

Objašnjenje:

Niz a, koji treba da se dobije kada generišete je 3, 4, 0, 5, 2, 8, 0, 2.