#P16056. [Oni2022国家队选拔赛]piezisa

[Oni2022国家队选拔赛]piezisa

题目描述

有一条街道,上面有 nn 家商店,编号为 0,1,…,n−10,1,\ldots,n-1。第 ii 家商店有一个整数值 viv_i。

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

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

x≤li≤ri≤y,x\le l_i\le r_i\le y,

并且

vx⊕vx+1⊕⋯⊕vy=0.v_x\oplus v_{x+1}\oplus\cdots\oplus v_y=0.

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

输入格式

第一行输入一个整数 nn。

第二行输入 nn 个整数 v0,v1,…,vn−1v_0,v_1,\ldots,v_{n-1}。

第三行输入一个整数 qq。

接下来 qq 行,每行输入两个整数 li,ril_i,r_i,表示一个询问区间。

输出格式

输出 qq 行。第 ii 行输出第 ii 个询问的答案。

数据范围与约束

  • 异或运算即 C/C++ 中的 ^;
  • 若不存在异或和为 00 且包含询问区间的连续段,答案为 −1-1;
  • 1≤n≤5000001\le n\le 500000;
  • 1≤q≤5000001\le q\le 500000;
  • 0≤vi<2300\le v_i<2^{30};
  • 0≤li≤ri<n0\le l_i\le r_i<n。

子任务

子任务 分值 限制
1 10 1≤n,q≤5001\le n,q\le 500
2 15 1≤n,q≤30001\le n,q\le 3000
3 5 对所有 ii,vi<4v_i<4
4 40 1≤n≤1000001\le n\le 100000
5 30 无额外限制

样例 1

输入

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

输出

2
1
5
2

解释

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

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

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

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

样例 2

输入

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

输出

8
4
-1

解释

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

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

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