7606: 宝石商店

在一家神秘的宝石工坊，工匠们研发了 $n$ 种独特的宝石配方，依次编号为 $1$ 到 $n$，每种配方的基础价值为 $a_i$。一天，工坊接待了 $q$ 位顾客，每位顾客携带 $x$ 元钱来定制宝石。工坊的定制规则是：顾客指定一个配方范围 $[l,r]$，工匠会从中挑选一种配方 $i$，通过魔法公式 $val = \left(a_i \lor x\right) \oplus \left(a_i \land x\right)$（其中 $\lor$ 表示按位或，$\oplus$ 表示按位异或，$\land$ 表示按位与）计算出配方的价值，然后选择价值最高的配方制作一颗价值为 $val$ 的宝石交给顾客。每位顾客的定制独立进行，配方的基础价值不会因任何定制而改变。 晚上，工匠发现账单遗失，只剩每位顾客的定制记录 $\left(l, r, x\right)$。请你帮工匠计算每位顾客获得的宝石价值。 --- 为了防止输入过大带来的常数问题，`C++` 选手请尽量使用关闭流同步的 `std::cin` 和 `std::cout` 实现输入输出，否则可能出现因读入输出问题导致的 TLE 等。 ```cpp int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); // your code return 0; } ```

第一行一个整数 $ T $ $ \left(1 \leq T \leq 10^6\right) $，表示测试数据组数。 对于每组数据，第一行包含两个用空格分隔的整数 $n, q$ $\left(1\le n,q\le 200000\right)$，表示宝石配方数量和顾客数量。 第二行包含 $n$ 个用空格分隔的整数 $a_i$ $\left(0\le a_i\le 2^{30}\right)$，表示每种配方的基础价值。 接下来 $q$ 行每行包含三个用空格分隔的整数 $l, r, x$ $\left(1\le l \le r \le n, 0\le x < 2^{30}\right)$，表示顾客选择的配方范围和携带的钱数。 保证所有测试数据的 $ n $ 之和不超过 $ 1265191 $，$ q $ 之和不超过 $ 2216368 $。

对于每组数据，输出 $q$ 行，每行一个整数，表示每位顾客获得的宝石价值。