공책

Ivan은 공책에 숫자를 적는다. 처음에 정수 집합 $S$가 공책에 적혀 있다. 그다음부터는 다음 연산으로 공책에 새 숫자를 적을 수 있다.

• $x$가 적혀 있으면 $2x$를 적을 수 있다.
• $x$가 적혀 있고 $x$가 $2$로 나누어떨어지면 $\frac{x}{2}$를 적을 수 있다.
• 서로 다른 두 수 $x$와 $y$가 적혀 있으면 $x \text{ xor } y$를 적을 수 있다.

시작 집합 $S$에 대해 Ivan이 공책에 적을 수 있는 가장 작은 수를 $f(S)$라고 하자.

길이가 $N$인 배열과 $Q$개의 질의가 주어진다. 각 질의는 다음 중 하나다.

• $a[x]$의 값을 $y$로 바꾼다.
• $f(\{a[L],a[L+1],\cdots,a[R]\})$의 값을 구한다.

첫째 줄에 $N$이 주어진다 ($N\leq 100000$). $N$은 배열의 길이이다.

둘째 줄에 $N$개의 정수 $a[1],a[2],\cdots,a[N]$이 주어진다 ($0<a[i]<2^{62}$). 이는 배열 $a$의 원소이다.

셋째 줄에 $Q$가 주어진다 ($Q\leq 100000$). $Q$는 질의의 수이다.

다음 $Q$개의 줄에 질의가 주어진다. 질의는 "$1$ $x$ $y$" 형식으로 $a[x]$ ($1\leq x\leq N$)를 $y$ ($0<y<2^{62}$)로 바꾸라는 것일 수도 있고, "$2$ $l$ $r$" 형식으로 $f(\{a[L],a[L+1],\cdots,a[R]\})$의 값을 구하라는 것일 수도 있다 ($1\leq L\leq R\leq N$).

두 번째 형식의 질의마다 $f(\{a[L],a[L+1],\cdots,a[R]\})$의 값을 한 줄에 출력한다.