ogrlice

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

Ulaz:<br><br>

(Ulazni podaci se ucitavaju sa standardnog ulaza) U prvom redu se nalazi broj n (n? 500000) koji predstavlja broj perli na krugu. U slede?em redu su dva broja, k i m (k? 10000, m? 10000000). U slede?ih k redova se nalazi po jedan ceo broj niza x[i] (x[i]? 2*m). Niz ai izra?unajte koriste?i doele navedeni segment programa (niz xi ima k elemenata i njhovi indeksi su od 0 do k-1, a ai ima n elemenata i njihovi indeksi su od 0 do n-1):<br><br>

<pre>
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;
}
</pre>
(% ozna?ava ostatak po modulu, a ^ ozna?ava bitovski xor) Za Pascal programere bi segment imao slede?i izgled:<br><br>
<pre>
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;
</pre><br><br>
U ovom kodu je xor oznaka za bitovnu eksluzivnu disjunkciju koja postoji kao operacija u Rascal-u. Broj ai predstavlja broj perli u niski ispod i-te perle na krugu. Rešenje ne zavisi od gornje formule, u njoj ne postoje zavisnosti koje bi vam pomogle u rešavanju. Ona služi da ulazna datoteka ne bude prevelika, da bi mogla da se u?ita u vremenskom ograni?enju.
<br><br>
Izlaz:<br><br>

(Izlazne podatke ispisati na standardni izlaz) U prvi red ispisati jedan ceo broj - broj perli u najve?em krugu koji se može dobiti jednim se?enjem i jednim spajanjem dve perle date ogrlice.<br><br>

Primeri:<br><br>
Ulaz:<br>
12<br>
12 5<br>
3<br>
0<br>
3<br>
2<br>
2<br>
0<br>
2<br>
0<br>
1<br>
0<br>
1<br>
0<br>
<br>
Izlaz:<br>
17<br>
<br>
Objašnjenje:<br>
<br>
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. i 3. perle, dobijamo dužinu 12 + 3 + 2 = 17.
<br><br>
Ulaz:<br>
8<br>
4 9<br>
3<br>
4<br>
0<br>
5<br>
Izlaz:<br>
20<br>
<br>
Objašnjenje:<br>
<br>
Niz a, koji treba da se dobije kada generišete je 3, 4, 0, 5, 2, 8, 0, 2.