题目描述

给定一个长度为 $n$ 的整数数组 $a$。定义

其中 & 表示按位与运算；当 $l>r$ 时，$f(l,r)$ 没有定义。

接下来有 $q$ 个询问。每个询问给出 $l,k$，请找出满足 $l\le r\le n$ 且 $f(l,r)\ge k$ 的最大下标 $r$。若不存在这样的 $r$，答案为 $-1$。

输入格式

第一行一个整数 $t$（$1\le t\le10^4$），表示测试组数。

对每组数据：

• 第一行一个整数 $n$（$1\le n\le2\cdot10^5$）；
• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le10^9$）；
• 第三行一个整数 $q$（$1\le q\le10^5$）；
• 接下来 $q$ 行，每行两个整数 $l,k$（$1\le l\le n$，$1\le k\le10^9$）。

保证所有测试组的 $n$ 之和不超过 $2\cdot10^5$，且 $q$ 之和不超过 $2\cdot10^5$。

输出格式

对每个询问，按输入顺序输出对应的最大 $r$；若不存在则输出 $-1$。

样例

样例 1

输入：

3
5
15 14 17 42 34
3
1 7
2 15
4 5
5
7 5 3 1 7
4
1 7
5 7
2 3
2 2
7
19 20 15 12 21 7 11
4
1 15
4 4
7 12
5 7

输出：

2 -1 5 
1 5 2 2 
2 6 -1 5