题目描述

给定两个长度为 $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

输入

3
1 2 3
4 5 6

输出

4

样例 2

输入

4
1 2 3 4
1 2 3 4

输出

24

样例 3

输入

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

输出

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

由 ChatGPT 4.1 翻译