Након што је сазнао да се породица Ватренић одселила из Ниша, господин Блажић може да престане да брине о својим оптичким кабловима и може да се посвети својој омиљеној игри са бројевима. Он је на поклон добио свеску са \(N\) природних бројева, и сваког од наредних \(Q\) дана планира да уради једну од две ствари:

1. Да замени \(p\)-ти број у свесци (тј. \(a_p\)) бројем \(x\).
2. Да за нека два броја \(l, r\) узме бројеве \(a_l, a_{l+1}, \ldots, a_r\) и са њима игра следећу игру:

Прво Блажић брише таблу а затим записује бројеве \(a_l, a_{l+1}, \ldots, a_r\) на ту таблу. Затим, ако је на табли један од записаних бројева број \(x\), он у једном потезу може да напише на таблу број \(2x\). Може да напише и број \(\frac x 2\) под условом да је \(x\) дељиво са \(2\). Такође, ако су на табли написани различити бројеви \(x, y\), он може да напише број \(x \text{ xor } y\) (за дефиницију операције \(\text{ xor }\) видети напомену). Притом, претходно записани бројеви се не бришу. Ваш задатак је да, сваки пут када господин Блажић игра игру, откријете који је најмањи природан број који може бити записан на табли након коначнo много потеза.

Опис улаза

Прва линија стандардног улаза садржи један природан број \(N\) - број бројева у свесци. Наредна линија садржи \(N\) природних бројева \(a_1, a_2 \ldots, a_N\), бројеве у свесци. Наредна линија садржи један природан број \(Q\) - број дана. Затим, \(j\)-та од наредних \(Q\) линија почиње бројем \(t_j\) - типом акције коју ће господин Блажић предузети \(j\)-тог дана. Уколико је \(t_j = 1\), следе два природна броја \(p_j, x_j\), који означавају да ће Блажић \(p_j\)-ти број у свесци заменити бројем \(x_j\). Уколико је \(t_j = 2\), следе два природна броја \(l_j, r_j\) и то значи да ће тог дана господин Блажић играти игру почевши од тренутних вредности бројева \(a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}\).

Опис излаза

За сваки дан када је \(t_j = 2\) у посебну линију стандардног излаза исписати један природан број - најмањи могућ број који се може добити на табли након коначнo много потеза ако се игра са бројевима из сегмента \([l_j, t_j]\).

Пример 1

Улаз

3
3 5 15
3
2 1 3
1 2 11
2 1 2

Излаз

3
1

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

Када господин Блажић први пут игра игру, игра почиње са бројевима \([3, 5, 15]\). Неки од бројева које Блажић може да напише на табли су \(6 = 3 \text{ xor } 5\), \(30 = 2 \cdot 15\), али, не постоји начин да запише број мањи од \(3\). Затим, Блажић замени број \(a_2 = 5\) бројем \(11\). Наредног дана он игра игру са бројевима \([3, 11]\). Он може добити број \(1\) на следећи начин: Прво направи \(8 = 3 \text{ xor } 11\) a затим дељењем са два добија редом бројеве \(4, 2, 1\).

Ограничења

У свим тест примерима важи: \(N, Q \leq 100000\), \(0 < a_i, x_j < 2^{62}\), \(t_j \in \{1, 2\}\), \(1 \leq l_j \leq r_j \leq N\), \(1 \leq p_j \leq N\), за свако \(1 \leq i \leq N, 1 \leq j \leq Q\).

• У тест примерима вредним 16 поена: \(N, Q \leq 100, a_i, x_j \leq 7\).
• У тест примерима вредним 28 поена: \(N, Q \leq 500\).
• У тест примерима вредним 56 поена: Нема додатних ограничења.

Напомена

Оператор \(\text{ xor }\) (ексклузивна дисјункција) у 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\).