题目描述

考虑一个有 $n$ 个元素的数组 $A$，其元素分别为 $A[i]$（$1 \le i \le n$）。接着给出两个整数 $Q$ 和 $K$，随后是 $Q$ 个查询。对于每个查询，你会得到 $L$ 和 $R$。你可以按照以下规则得到 $Z$。

为了得到 $Z$，首先你需要从 $A[L]$ 到 $A[R]$ 中选择若干个元素，我们称之为 $A[i_1], A[i_2], \dots, A[i_t]$。然后，你可以令 $Z$ 等于 $K$ 按位或 $(A[i_1] \text{ xor } A[i_2] \text{ xor } \dots \text{ xor } A[i_t])$。

请对每个查询求出最大的 $Z$。

输入格式

多组测试数据。

第一行是一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。接下来是 $T$ 组测试数据。每组数据以三个整数 $N$、$Q$、$K$ 开始（$1 \le N \le 10000$，$1 \le Q \le 100000$，$0 \le K \le 100000$）。接下来一行包含 $N$ 个整数，依次表示 $A[1]$ 到 $A[N]$（$0 \le A[i] \le 10^8$）。随后是 $Q$ 行，每行包含两个整数 $L$ 和 $R$（$1 \le L \le R \le N$）。

输出格式

对于每个查询，在一行中输出答案。

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

3
7
7

提示

翻译由 DeepSeek V4 Pro 完成