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