题目描述

给定一个包含 $N$ 个整数的数组 $A$：$[A_1, A_2, \dots, A_N]$。

如果可以通过重排 $A$，使得对于所有满足 $1 \leq i < j \leq N$ 的 $(i, j)$ 对，在重排后都满足以下两个条件：$A_i \oplus p \leq A_j \oplus q$ 且 $A_i \oplus q \leq A_j \oplus p$，则称数组 $A$ 是 $(p, q)$-xorderable 的。其中运算符 $\oplus$ 表示按位异或。

给定另一个长度为 $M$ 的数组 $X$：$[X_1, X_2, \dots, X_M]$。请计算满足 $1 \leq u < v \leq M$ 且数组 $A$ 是 $(X_u, X_v)$-xorderable 的 $(u, v)$ 对的数量。

输入格式

第一行包含两个整数 $N$ $M$（$2 \leq N, M \leq 200\,000$）。

第二行包含 $N$ 个整数 $A_i$（$0 \leq A_i < 2^{30}$）。

第三行包含 $M$ 个整数 $X_u$（$0 \leq X_u < 2^{30}$）。

输出格式

输出一个整数，表示满足 $1 \leq u < v \leq M$ 且数组 $A$ 是 $(X_u, X_v)$-xorderable 的 $(u, v)$ 对的数量。

3 4
0 3 0
1 2 1 1

3

5 2
0 7 13 22 24
12 10

1

3 3
0 0 0
1 2 3

0

提示

样例输入/输出 #1 的解释

数组 $A$ 是 $(1, 1)$-xorderable 的，可以通过将数组 $A$ 重排为 $[0, 0, 3]$ 来实现。

样例输入/输出 #2 的解释

数组 $A$ 是 $(12, 10)$-xorderable 的，可以通过将数组 $A$ 重排为 $[13, 0, 7, 24, 22]$ 来实现。

翻译由 DeepSeek V3.2 完成