Познати јунак из познатог модерног суперхеројског стрипа “Битовске операције против Мусе Кесеџије”, Ксорко, је у најновијем поглављу упао у незгодну клопку и сада му је живот у великој опасности! Међутим, како то обично бива у стриповима едукативног карактера, он се може извући и то само уз вашу помоћ!

Ксорко пред собом има низ ненегативних целих бројева \(A_1,A_2\cdots,A_N\) дужине \(N\). Како је Муса заповедио, Ксорко може да мења елементе овог низа по следећем правилу: у једном потезу бира природан број \(1<i<N\) и мења вредности бројева \(A_{i-1}\) и \(A_{i+1}\) у \((A_{i-1}\text{ xor }A_i)\) и \((A_{i+1}\text{ xor }A_i)\) редом, где \(\text{xor}\) представља операцију битовске ексклузије. Како њему треба врло јак низ да би побегао, он жели да примени дату операцију неки број пута тако да добијени низ буде лексикографски највећи могући.

Ви, као верни обожаваоци овог стрипа, нестрпљиво чекате следеће поглавље, које неће изаћи док неко не реши Ксорков проблем. Стога, на вама је да спасете Ксорка и омогућите наставак овој епској причи. ## Описи функција

Потребно је да имплементирате функцију

• \(LexMax(N, A[\ldots], B[\ldots])\)

где је \(N\) број који представља број елемената Ксорковог низа, а тај низ је управо \(A\). У низ \(B\) дужине \(N\) треба да упишете вредности бројева који ће се налазити у Ксорковом низу на крају. Сви низови су индексирани од 1.

Пример

Нека је \(N=3\), и нека је низ \(A=\{1,3,2\}\): тада једина операција коју можемо да извршимо је да изаберемо \(i=2\) и заменимо \(1\) и \(2\) са \((1 \text{ xor } 3)=2\) i \((2 \text{ xor } 3)=1\). Тиме добијамо лексикографски јачи низ низ \(\{2,3,1\}\). Ако применимо операцију опет, враћамо се у почетно стање па треа вратити \(B=\{2,3,1\}\).

Нека је \(N=5\), и нека је низ \(A=\{31,31,31,31,31\}\). Применом било каквих операција на овај низ није могуће добити већи низ, па треба вратити \(B=\{31,31,31,31,31\}\).

Ограничења

• \(1 \leq N \leq 150.000\)
• \(0 \leq A_i \leq 10^{18}\)

Подзадаци

Тест примери су подељени у \(6\) подзадатка:

• [6 поена]: \(N\leq10\), \(A_i\leq 1\)
• [7 поена]: \(N\leq10\), \(A_i\leq 63\)
• [12 поена]: \(A_i\leq1\)
• [21 поена]: \(N\leq3000\)
• [22 поена]: \(A_i\leq15\)
• [32 поена]: Нема додатних ограничења

Детаљи имплементације

Потребно је да пошаљете тачно један фајл xorko.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

void LexMax(int N, int* A, int* B);

Вашим програмима је дозвољено да мењају садржај низова али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду број \(N\).
• У наредном реду \(N\) ненегативних целих броја \(A_i\).

Затим овај програм зове вашу функцију и штампа \(N\) бројева које представљају решење које врати функција. ## Напомена Оператор ексклузивне дисјункције у 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\).

Кажемо да је низ \(P\) лексикографски мањи од низа \(Q\) исте дужине ако важи да је \(P_i < Q_i\) за најмање \(i\) за које је \(P_i \neq Q_i\).