给$n$个数字$a_1, a_2, \dots, a_n$。
对于每个$r$,你要找到一个$l(1\leq l\leq r)$,使得$a_l~\mathrm{xor}~a_{l+1}~\mathrm{xor}~\dots~\mathrm{xor}~a_r$最大。如果有多个选择,找到最大的$l$。
输入格式
第一行一个整数$n$。
接下来一行,若干个整数$a_1, a_2, \dots, a_n$。
输出格式
输出$n$行,对于每行,输出两个数字,分别表示它们的最大的$\mathrm{xor}$和,和对应的最大的$l$。
样例输入
5
1 2 3 4 5
样例输出
1 1
3 1
3 3
7 3
5 5
数据规模
对于$100\%$的数据,保证$1\leq n \leq 2 \times 10^5, 0\leq a_i \leq 2^{30}-1$。