Претходних година, дуологија о великом шефу мафије ексклузивне дисјункције Окрам Ћивас постали су неки од најпопуларнијих и највољенијих филмова на тржишту. Дуологија се састоји од, као што име каже, два филма, који се зову Окрам и Ћивас. У овом задатку бавићемо се другим делом дуологије - Ћивасом.

У најновијој авантури нашег хероја, он се нашао на тајанственој кружној траци. Ова трака је подељена на \(N\) делова, који су редом нумерисани бројевима од \(1\) до \(N\), а у сваком делу траке се налазио по један ненегативан цео број. Број у \(i\)-том делу круга означавамо са \(A_i\). Није ни стигао да се прибере кад су кренули да се мењају бројеви по траци. Десило се \(Q\) промена, где се у \(i\)-тој промени, број у делу траке са ознаком \(p_i\) променио у нову вредност \(v_i\). Сви озбиљнији филмофили могли су да уоче да важи нешто интересантно: ни у једном тренутку није постојао број \(D<N\) тако да је кружни низ \(A_i\) био \(D\)-периодичан (то јест не постоји \(D\) тако да свака два дела на дистанци \(D\) имају исти број написан на себи, тј. \(A_i=A_{(i+D) \text{mod }N}\)). Из неког разлога је између свака два дела траке \(i\) и \(i+1\) писао број \(B_i\) који је био једнак ексклузивној дисјункцији (познатој и као xor) два броја написана на та два дела (прецизније \(B_i=A_i\text{ xor }A_{i+1}\)). Променама вредности \(A_i\) су се, наравно, мељале и вредности \(B_i\).

Како је Окрам Ћивас познат по својој мајсторији са ексклузивном дисјункцијом, он је себи задао следећи задатак: Пре свих промена, као и после сваке промене, желео је да нађе периоду кружног низа \(B\), то јест најмањи природан број \(D\) тако да важи \(B_i=B_{(i+D)\text{ mod }N}\).

Опис улаза

Прва линија стандардног улаза садржи два броја, број делова траке \(N\) и број упита \(Q\). У наредној линији налази се \(N\) природних бројева: где \(i\)-ти број представља број \(S_i\), који означава почетну вредност броја у \(i\)-том делу траке. Наредних \(Q\) линија садрже по два броја: \(p_i,v_i\), који представљају промену вредности у низу \(A\) из текста.

Опис излаза

На стандардни излаз је потребно исписати \(Q+1\) линија: у првој линији треба наћи периоду пре икаквих упита, а у \(i+1\)-ој линији треба наћи периоду после \(i\)-те промене.

Пример 1

Улаз

6 1
0 1 3 1 0 1
6 2

Излаз

6
3

Пример 2

Улаз

5 2
2 3 4 1 2
3 3
4 4

Излаз

5
5
5

Објашњења примера

У првом примеру је низ \(B\) на почетку 1 2 2 1 1 1, чија је најмања периода очито цео низ, док после промене низ је 1 2 2 1 2 2, када је \(3\) периодично.

У другом примеру како је \(5\) прост, а период дели дужину низа, важи да је период увек \(1\) или \(5\), а како овде никад није \(1\) онда је одговор \(5\) после сваке промене. ## Ограничења - \(2 \leq N,M \leq 200.000\) - \(1\leq Q\leq 200.000\) - \(0\leq A_i,v_i<2^{30}\) - \(1\leq p_i\leq N\)

Тест примери су подељени у 5 дисјунктних група:

• У тест примерима вредним \(10\) поена: \(N\leq500\) и \(Q\leq 500\)
• У тест примерима вредним \(20\) поена: \(Q\leq25\)
• У тест примерима вредним \(30\) поена: \(Q\leq3.000\)
• У тест примерима вредним \(40\) поена: Без додатних ограничења ## Напомена

Оператор ексклузивне дисјункције у Pascal-u је означен са xor, док у C++ га записујемо помоћу симбола ^. Ова операција \(x\ \text{xor} \ y​\) се за ненегативне целе бројеве \(x,y​\) дефинише на следећи начин. Прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са \(a_1, \ldots, a_k​\) и \(b_1, \ldots b_k​\). Затим се за сваку позицију \(i \in {1, \ldots, k }​\) рачуна \(c_i​\) помоћу следећих правила:

• За \(a_{i} = 0, b_{i} = 0\) важи \(c_{i} = 0\)
• За \(a_{i} = 0, b_{i} = 1\) важи \(c_{i} = 1\)
• За \(a_{i} = 1, b_{i} = 0\) важи \(c_{i} = 1\)
• За \(a_{i} = 1, b_{i} = 1\) важи \(c_{i} = 0\)

Низ бинарних цифара \(c_1, \ldots, c_k\) (који можда има водеће нуле) је бинарни запис резултата, односно броја \(x \ \text{xor} \ y\).

Ако желите да сазнате причу о пореклу нашег хероја, погледајте трећи задатак за \(B\) категорију: Окрам