题目背景

出题人给了你一个有魔法的序列。

题目描述

设出题人给你的魔法序列为 $b$。此外，出题人还给了你一个初始序列 $a$，并保证序列 $a$ 单调递增。

最初 $b = a$。由于有魔法，序列 $b$ 会发生一些变化，具体而言，在第 $x$ 秒时 $b_i = a_i \oplus x$，这里 $\oplus$ 代表按位或。

现在给你 $q$ 次询问，每次询问给定 $l,r,x$，你需要回答第 $x$ 秒时 $\max_{l \leq i \leq r} b_i$ 是多少。

输入格式

第一行一个数 $n$ 表示序列长度，接下来一行 $n$ 个数表示初始序列 $a$。

再接下来一行一个数 $q$，接下来 $q$ 行每行三个数 $l,r,x$ 表示一次询问。

输出格式

对于每次询问输出一行一个答案。

样例 #1

样例输入 #1

5
0 2 5 14 155
5
2 3 2
2 5 114
3 5 514
1 5 0
1 3 234

样例输出 #1

7
251
667
155
239

样例 #2

exC.in

exC.out

提示

对于 $100\%$ 的数据，保证 $1 \leq n,q < 2^{20},0 \leq x,a_i < 2^{20}$。