33128번 - Xorderable Array 다국어

You are given an array $A$ of $N$ integers: $[A_1, A_2, \dots , A_N ]$.

The array $A$ is $(p, q)$-xorderable if it is possible to rearrange $A$ such that for each pair $(i, j)$ that satisfies $1 ≤ i < j ≤ N$, the following conditions must be satisfied after the rearrangement: $A_i \oplus p ≤ A_j \oplus q$ and $A_i \oplus q ≤ A_j \oplus p$. The operator $\oplus$ represents the bitwise xor.

You are given another array $X$ of length $M$: $[X_1, X_2, \dots , X_M]$. Calculate the number of pairs $(u, v)$ where array $A$ is $(X_u, X_v)$-xorderable for $1 ≤ u < v ≤ M$.

The first line consists of two integers $N$ $M$ ($2 ≤ N, M ≤ 200\, 000$).

The second line consists of $N$ integers $A_i$ ($0 ≤ A_i < 2^{30}$).

The third line consists of $M$ integers $X_u$ ($0 ≤ X_u < 2^{30}$).

Output a single integer representing the number of pairs $(u, v)$ where array $A$ is $(X_u, X_v)$-xorderable for $1 ≤ u < v ≤ M$.