题目描述

有一条街道，上面有 $n$ 家商店，编号为 $0,1,\ldots,n-1$。第 $i$ 家商店有一个整数值 $v_i$。

Alex 有 $q$ 个计划。第 $i$ 个计划给出一个区间 $[l_i,r_i]$，表示他至少想访问这个连续区间内的所有商店。

Alex 很迷信：他希望实际访问的连续区间中所有 $v$ 的异或和为 $0$。因此，对于每个计划 $[l_i,r_i]$，你需要找到一个长度最短的区间 $[x,y]$，满足：

并且

输出这个最短长度。如果不存在这样的区间，则输出 $-1$。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $v_0,v_1,\ldots,v_{n-1}$。

第三行输入一个整数 $q$。

接下来 $q$ 行，每行输入两个整数 $l_i,r_i$，表示一个询问区间。

输出格式

输出 $q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

数据范围与约束

• 异或运算即 C/C++ 中的 ^；
• 若不存在异或和为 $0$ 且包含询问区间的连续段，答案为 $-1$；
• $1\le n\le 500000$；
• $1\le q\le 500000$；
• $0\le v_i<2^{30}$；
• $0\le l_i\le r_i<n$。

子任务

样例 1

输入

6
2 0 3 3 2 2
4
5 5
1 1
0 1
2 2

输出

2
1
5
2

解释

对于第一个计划 $[5,5]$，商店 $5$ 的值为 $2$。区间 $[4,5]$ 的值为 $2,2$，异或和为 $0$，且长度最短，因此答案为 $2$。

对于第二个计划 $[1,1]$，商店 $1$ 的值为 $0$，区间 $[1,1]$ 本身异或和为 $0$，答案为 $1$。

对于第三个计划 $[0,1]$，最优区间为 $[0,4]$，长度为 $5$。

对于第四个计划 $[2,2]$，最优区间为 $[2,3]$，长度为 $2$。

样例 2

输入

10
5 7 3 6 1 2 5 2 5 4
3
7 9
5 8
1 5

输出

8
4
-1

解释

对于第一个计划，一个最优区间是 $[2,9]$，长度为 $8$。

对于第二个计划，一个最优区间是 $[5,8]$，长度为 $4$。

对于第三个计划，不存在合法区间，因此输出 $-1$。