D. We need more and more OR numbers
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的序列 $$$a$$$，序列中的数字都是正整数，你需要完成一段代码，完成以下两种操作：

$$$1$$$ $$$l$$$ $$$r$$$：将序列中所有下标范围为 $$$[l,r](1\le l \le r\le n)$$$ 的数字变成它的或数。

$$$2$$$ $$$pos$$$：询问当前下标为 $$$pos$$$ 的数字是多少。

一个数字的或数是指将一个正整数的的十进制的表示形式每个数位按位或操作之后的结果，例如，数字 $$$25_{10}$$$ 的或数就是 $$$7_{10}$$$，因为 $$$2_{10}\ OR\ 5_{10}=7_{10}$$$。

举个例子，令 $$$fOR(x)$$$ 代表 $$$x$$$ 的或数，那么 $$$fOR(11)=1,fOR(45)=5,fOR(14)=5,fOR(520)=7$$$。

Input

第一行，一个整数 $$$t(1\le t \le 10^5)$$$，代表数据组数。

对于每组数据：

第一行，一个整数 $$$n(1\le n \le 5·10^5)$$$，代表序列中数字的数量。

第二行，$$$n$$$ 个整数 $$$a(1\le a \le 10^9)$$$，代表这个序列。 第三行，一个整数 $$$q(1\le q \le 5·10^5)$$$，代表操作次数。

接下来的 $$$q$$$ 行，每行为一个题目中给出的操作。

保证在同一测试点内的 $$$\sum n \le 10^6;\sum q \le 10^6$$$。

Output

对于每个第 $$$2$$$ 种询问，输出一行整数表示答案。

Example
Input
2
6
11 45 14 520 1314 12345678
11
1 1 3
2 4
2 2
1 3 6
2 6
2 2
2 1
1 4 4
2 3
2 4
2 5
3
2 4 6
4
1 1 3
2 1
2 2
2 3
Output
520
5
15
5
1
5
7
7
2
4
6