For the first subtask, it suffices to try possible values of ~c~ less than ~2^{15}~. The resulting multisets can be compared with sorting in ~\mathcal O(N \log N)~.

Time complexity: ~\mathcal O(\max A \cdot N \log N)~

For the second subtask, we observe that if a value for ~c~ exists, there is some ~A_i~ such that ~A_i \oplus c = B_1~, meaning ~c = A_i \oplus B_1~. With this, we have ~2N+1~ possible candidates for ~c~: ~A_1 \oplus B_1, A_2 \oplus B_1, \dots, A_{2N+1} \oplus B_1~.

Time complexity: ~\mathcal O(N^2 \log N)~

For the final subtask, we will use the fact that ~2N+1~ is odd. Let's begin by assuming that we have found a value of ~c~ which makes the multisets equal. This implies that:

$$\displaystyle A_1 \oplus c \oplus A_2 \oplus c \oplus \dots \oplus A_{2N+1} \oplus c = B_1 \oplus B_2 \oplus \dots \oplus B_{2N+1}$$

Let's XOR both sides by ~A_1 \oplus A_2 \oplus \dots \oplus A_{2N+1}~:

$$\displaystyle c \oplus c \oplus \dots \oplus c = B_1 \oplus B_2 \oplus \dots \oplus B_{2N+1} \oplus A_1 \oplus A_2 \oplus \dots \oplus A_{2N+1}$$

The left hand side has an odd number of copies of ~c~, so we have:

$$\displaystyle c = B_1 \oplus B_2 \oplus \dots \oplus B_{2N+1} \oplus A_1 \oplus A_2 \oplus \dots \oplus A_{2N+1}$$

We have proven if a solution exists, then it is unique and given by the expression above. All that remains is to check if this value of ~c~ works.

Time complexity: ~\mathcal O(N \log N)~