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 nalaze u datoteci ogrlica.in) U prvom redu ulazne datoteke 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 a_i izračunajte koristeći doele navedeni segment programa (niz x_i ima k elemenata i njhovi indeksi su od 0 do k-1, a a_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 disjunkciju koja postoji kao operacija u Rascal-u. Broj a_i 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.

Izlaz:

(Izlazne podatke upisati u datoteku ogrlica.out) U prvi red izlazne datoteke 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.

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

#include <stdio.h>

const int maxn = 1000000;

int x[200];
int a[maxn];
int best[2*maxn];
int koji[2*maxn];

void gen(int* x, int k, int* p, int n, int m) {            
      int i,j = 0;    
      for (i = 0; i < n; i++) {
          a[i] = x[j];
          printf("niz %d\n", a[i]);
          int s = (j+1) % k;
          x[j] = ((x[j] ^ x[s]) + 13) % m;
          j = s;
      }         
}

int main() {
    int i,j,k,n,m,poc,kraj,res;
    freopen("ogrlica.in","r",stdin);
    freopen("ogrlica.out","w",stdout);
    
    scanf("%d", &n);
    scanf("%d %d", &k, &m);
    for (i=0;i<k;i++)
        scanf("%d", &(x[i]));
    
    gen(x,k,a,n,m);
    
    
    best[0] = n + a[0];
    koji[0] = 0;
    poc = 0;
    kraj = 0;

    
    for (i=1;i<n;i++)  
    {
        while (kraj >=poc && best[kraj]<n-i+a[i])
              kraj--;
        kraj++;
        best[kraj] = n-i+a[i];   
        koji[kraj] = i;   
    }    

    res = a[n-1] + best[poc];
    
    for (i = 0;i<n;i++)
    {
        if (koji[poc]==i)
           poc++;
        while (kraj >=poc && best[kraj]<-i+a[i])
              kraj--;              
              
        kraj++;
        best[kraj] = -i+a[i];   
        koji[kraj] = i; 
        
        int tr = a[i] + i + 1 + best[poc];       
        res = res>tr?res:tr;           
    }
    
    printf("%d\n", res);
    return 0;   
}