Xor Sum 4.5

※この問題は $O(N^2)$ 解を通さないよう、想定解に対して制約が非常に厳しくなっています。C++などの高速な言語を利用することを強く推奨します。参考までに、writer解はC++で648msです。

問題文

それぞれ長さが $N$ の整数列 $A=(A_1,A_2,\ldots,A_N) , B=(B_1,B_2,\ldots,B_N)$ が与えられます。
あなたは以下の操作を何回でも行うことが出来ます。

• $B$ を左巡回シフトする。つまり、 $B=(B_1,B_2,\ldots,B_{N-1},B_N)$ を $B'=(B_2,B_3,\ldots,B_N,B_1)$ で置き換える。

操作を行う回数をうまく決めることによって達成出来る、以下の式の値の最大値を求めてください。

• $\sum_{i=1}^{N} (A_i$ $xor$ $B_i)$

ただし、 $a$ $xor$ $b$ は $a$ と $b$ のbitごとの排他的論理和を表します。

制約

• $1\leq N \leq 170000$
• $0 \leq A_i,B_i \leq 10^3$
• 入力は全て整数 　　

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを出力してください。

入力例1

3
4 1 8
2 6 9

出力例1

30

操作を $2$ 回行うと、 $B$ は $(2,6,9)→(6,9,2)→(9,2,6)$ と変化します。
このとき、式の値は $(4$ $xor$ $9)+(1$ $xor$ $2)+(8$ $xor$ $6)=13+3+14=30$ となり、これが達成できる値の最大値です。

入力例2

2
1 0
0 1

出力例2

2

$1$ 回も操作を行わないのが最適です。

入力例3

13
689 12 487 496 126 874 327 0 12 35 352 546 249
445 124 124 346 523 918 576 986 978 144 276 444 11

出力例3

7514