There are \(2^N - 1\) ways to choose one or more cards, which will be enormous when \(N\) is large. However, there are \(2^{30}\) possible values of the XORs (exclusive logical sums) of \(A_i\) and \(B_i\) under the Constraint of this problem, the number of whose pairs is \(2^{30} \times 2^{30} = 2^{60}\). Here, let’s hypothesise that “we do not have to consider all the \(N\) cards, but all the ways of selections can be expressed by about 60 cards.

For distinct Cards \(i\) and \(j\), replacing \(A_j\) with \(A_i \oplus A_j\) and \(B_j\) with \(B_i \oplus B_j\) does not change the answer, which can be understood by the following observations:

• Choosing Card \(j\) before the replacement is equivalent to choosing Cards \(i\) and \(j\) after the replacement.
• Choosing Cards \(i\) and \(j\) before the replacement is equivalent to choosing Card \(j\) after the replacement.

Consider a matrix where the \(i\)-th (\(1 \leq i \leq N\)) row contains the binary notation of \(A_i\) and the binary notation of \(B_i\). The matrix corresponding to Sample Input \(1\) is as follows.

\[\left(\begin{array}{cc|cc} 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right)\]

Operations like “replacing rows \(i\) and \(j\)” and “replacing each element of row \(i\) with the XOR with that of row \(i\)” (which are called elementary row operations) do not change the answer. With these operations, let us transform this matrix to a step matrix. A step matrix is such matrix that the column index where the non-zero element exists is (strictly) monotonically increasing with respect to the row index. Here is an example of such operation.

The matrix has been transformed to the following step matrix.

\[\left(\begin{array}{cc|cc} 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array}\right)\]

Since \(A_i, B_i \leq 2^{30}\), we can assume that there are at most \(30 + 30 = 60\) rows. Also, in a step matrix, the number of rows where a non-zero element exists does not exceed the number of columns, so after the transformation, \(A_i = B_i = 0\) for all rows except for at most \(60\) rows. Therefore, we have shown that we have to consider at most \(60\) cards.

Let us determine for each card (such that \(A_i \neq 0\)) from the top row of the matrix to the bottom if we should choose the card. Let \(A'\) and \(B'\) denote the XORs of the cards that have already been chosen.

Let \(k\) be the maximum integer such that \(2^k \leq A_i\). \(2^k\) is the most significant bit in \(A_i\). When Card \(i+1\) or later card is chosen, only the bits in the \(1, 2, \dots\), and \(2^{k - 1}\)’s place can change. Therefore, if “\(A'\) will never exceed \(K\) even if its \(1, 2, \dots, 2^{k - 1}\)’s places are all \(1\),” then we can arbitrarily choose Card \(i+1\) and later.

For each \(i = 1, 2, \dots\), do the following.

• If \(A' \cup (2^k - 1) \leq K\), then compute the maximum value when we do not choose Card \(i\) and we may choose Card \(i+1\) and any later cards, and let it be a candidate of the answer. Later on, we will compute the maximum value when Card \(i\) is chosen, replace \(A'\) with \(A' \oplus A_i\) and \(B'\) with \(B' \oplus B_i\).
• If \((A' \oplus A_i) \cup (2^k - 1) \leq K\), then compute the maximum value when we do choose Card \(i\) and we may choose Card \(i+1\) and any later cards, and let it be a candidate of the answer. Later on, we will compute the maximum value when Card \(i\) is not chosen, so we keep \(A'\) and \(B'\) unchanged.
• If neither of the two is satisfied, then determine if we should choose \(A_i\) so that \(2^k\)’s place will be \(0\), since if \(2^k\)’s place is \(1\), the XOR of the numbers written on the front will always exceed \(K\).

Now, all the left is to solve the following subproblem.

Given integers \(B', B_1, \dots, B_m\), maximize the XOR of some of \(B_1, \dots, B_m\) and \(B'\).

For \(B_1, \dots, B_m\), consider the same matrix as before, and transform it to a step matrix with elementary row operation. Then, from the top row to the bottom, replace \(B'\) with the larger of \(B'\) and \(B' \oplus B_i\), and the resulting \(B'\) is the maximum value.

The solution above can be implemented in about \(O(NW + W^3)\) time, where \(W = \log(\max (A_1, \dots, A_N, B_1, \dots, B_N))\).

Sample code (C++) :