시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 2 1 1 100.000%

문제

You are given an array $a$ of size $n$ and you need to perform $m$ queries on it. There are three types of queries:

  1. "& $l$ $r$ $x$": change $a_i$ to ($a_i$ AND $x$) for all $i$ = $l$, $l+1$, $\ldots$, $r$;
  2. "| $l$ $r$ $x$": change $a_i$ to ($a_i$ OR $x$) for all $i$ = $l$, $l+1$, $\ldots$, $r$;
  3. "? $l$ $r$": find the minimal value among $a_l$, $a_{l+1}$, $\ldots$, $a_r$.

Output the answers for all queries of the third type.

입력

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) --- the size of the array.

The second line contains $n$ space-separated integers $a_i$ ($0 \le a_i < 2^{30}$) --- the elements of the array.

The third line contains one integer $m$ ($1 \le m \le 2 \cdot 10^5$) --- the number of queries.

Next $m$ lines contain descriptions of queries in the format described above. For all queries $1 \le l \le r \le n$, for queries of the first and second types $0 \le x < 2^{30}$.

출력

For each query of the third type, print the answer on a separate line.

예제 입력 1

5
1 2 3 4 5
4
& 1 2 6
| 3 5 4
? 1 2
? 3 5

예제 출력 1

0
4