CF1100F Ivan and Burgers

Ivan 喜欢汉堡和花钱。在 Ivan 所住的街道上有 $n$ 家汉堡店。Ivan 有 $q$ 个朋友，第 $i$ 个朋友建议在第 $l_i$ 家汉堡店见面，然后一起走到第 $r_i$ 家汉堡店（$l_i \leq r_i$）。在和第 $i$ 个朋友散步的过程中，Ivan 可以访问所有满足 $l_i \leq x \leq r_i$ 的汉堡店 $x$。 对于每家汉堡店，Ivan 都知道其中最贵的汉堡价格，记为 $c_i$ burles。Ivan 想在路上选择一些汉堡店，每到一家就买最贵的汉堡，并且花掉最多的钱。但有个小问题：他的银行卡坏了，每次消费后卡上的金额变化如下。 如果消费前 Ivan 有 $d$ burles，在汉堡店消费了 $c$ burles，那么消费后他卡上的余额会变成 $d \oplus c$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 目前 Ivan 卡上有 $2^{2^{100}} - 1$ burles，他想和朋友们一起散步。请你帮他计算：如果和第 $i$ 个朋友一起散步，他最多能花掉多少钱？他花掉的钱定义为初始金额减去最终金额。

第一行包含一个整数 $n$（$1 \leq n \leq 500\,000$），表示汉堡店的数量。 第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$0 \leq c_i \leq 10^6$），其中 $c_i$ 表示第 $i$ 家汉堡店最贵的汉堡价格。 第三行包含一个整数 $q$（$1 \leq q \leq 500\,000$），表示 Ivan 的朋友数量。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示 Ivan 和朋友将要走过的汉堡店区间。

输出 $q$ 行，第 $i$ 行输出 Ivan 和第 $i$ 个朋友一起散步时最多能花掉的钱。

在第一个测试中，为了和第一个和第三个朋友花掉最多的钱，Ivan 只需要进入第一家汉堡店。和第二个朋友时，Ivan 只需要进入第三家汉堡店。 在第二个测试中，对于第三个朋友（从第一家走到第三家），一共有 8 种花钱方式——$0$、$12$、$14$、$23$、$12 \oplus 14 = 2$、$14 \oplus 23 = 25$、$12 \oplus 23 = 27$、$12 \oplus 14 \oplus 23 = 20$。最大能花掉的钱是 $12 \oplus 23 = 27$，也就是进入第一家和第三家汉堡店。 由 ChatGPT 4.1 翻译