题目描述

给定两个长度为 $N$ 的整数序列 $(A_1, A_2, \cdots, A_N)$ 和 $(B_1, B_2, \cdots, B_N)$。

请计算 $\sum_{1 \leq i < j \leq N} \min(A_i \oplus A_j, B_i \oplus B_j)$ 的值。其中，$\oplus$ 表示按位异或运算。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 2 3
4 5 6

输出 #1

4

输入输出样例 #2

输入 #2

4
1 2 3 4
1 2 3 4

输出 #2

24

输入输出样例 #3

输入 #3

10
195247 210567 149398 9678 23694 46151 187762 17915 176476 249828
68649 128425 249346 62366 194119 117620 26327 161384 207 57656

输出 #3

4019496

说明/提示

限制条件

• $1 \leq N \leq 250000$
• $0 \leq A_i, B_i < 2^{18}$
• 输入的所有值均为整数。

样例解释 1

• $\min(1 \oplus 2, 4 \oplus 5) = \min(3, 1) = 1$
• $\min(1 \oplus 3, 4 \oplus 6) = \min(2, 2) = 2$
• $\min(2 \oplus 3, 5 \oplus 6) = \min(1, 3) = 1$ 因此，答案为 $1 + 2 + 1 = 4$。