Logo Daimayuan Online Judge

Home

时间限制:2 s 空间限制:1024 MB

#51. 最大异或和

附加文件 统计

给$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$。