\(1\) 枚以上のカードを好きに選ぶ方法は \(2^N - 1\) 通りあり、これは \(N\) が大きいとき莫大な数になります。しかし、\(A_i, B_i\) の排他的論理和はこの問題の制約下で \(2^{30}\) 通りの値しかとらず、これらの組は高々 \(2^{30} \times 2^{30} = 2^{60}\) 通りです。ここで、「実は \(N\) 枚のカードを全て考える必要はなく、\(60\) 枚程度のカードのの組合せで全ての選び方が表現できるのではないか」と予想してみましょう。

異なるカード \(i, j\) に対し、\(A_j\) を \(A_i \oplus A_j\) で、\(B_j\) を \(B_i \oplus B_j\) で置き換えても答えは変わりません、これは以下の考察からわかります。

• 置き換える前のカード \(j\) を選ぶことは、置き換えた後のカード \(i, j\) を両方選ぶことに対応する。
• 置き換える前のカード \(i, j\) を両方選ぶことは、置き換えた後のカード \(j\) を選ぶことに対応する。

\(i \, (1 \leq i \leq N)\) 行目に \(A_i\) の二進表記と \(B_i\) の二進表記が並んでいるような行列を考えます。入力例 \(1\) に対応する行列は以下のようになります。

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

「行 \(i, j\) を入れ替える」「行 \(j\) の各成分を行 \(i\) との排他的論理和で置き換える」という操作（行基本操作）をしても答えは変わりません。これらの操作によって、行列を階段行列に変形しましょう。階段行列とは、各行において最左の非零成分が存在する列番号が、行番号について（狭義）単調増加であるようなものをいいます。以下に操作の一例を示します。

次のような階段行列に変形することができました。

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

\(A_i, B_i \leq 2^{30}\) より、行列の列数は \(30 + 30 = 60\) 以下としてよいです。また、階段行列において非零成分が存在する行の個数は列数以下であるので、変形を施した後は、高々 \(60\) 個の行を除いて残りは全て \(A_i = B_i = 0\) となります。以上により、高々 \(60\) 枚のカードのみを考慮すればよいことがわかります。

これらのカード（のうち、\(A_i \neq 0\) であるもの）を、行列において上の行に存在するものから順に選ぶかどうかを決めていきます。既に選ぶことに決めたカードについての \(A_i, B_i\) の排他的論理和をそれぞれ \(A', B'\) と表します。

\(k\) を \(2^k \leq A_i\) となる最大の整数とします。\(2^k\) は \(A_i\) の最上位ビットです。カード \(i + 1\) 以降を選んだときに変化するのは \(1, 2, \dots, 2^{k - 1}\) の位のビットのみです。よって、カード \(i\) を選ぶかどうか決めた時点で「\(1, 2, \dots, 2^{k - 1}\) の位が全て \(1\) だったとしても \(K\) 以下になる」となったならば、カード \(i + 1\) 以降はどのように選んでもよいということになります。

\(i = 1, 2, \dots\) の順に以下の処理を行います。

• \(A' \cup (2^k - 1) \leq K\) ならば、カード \(i\) は必ず選ばず、カード \(i+1\) 以降はどのように選んでもよいとしたときの最大値を計算して答えの候補とする。その後、カード \(i\) を選ぶ場合の最大値を計算するため、\(A'\) を \(A' \oplus A_i\) で、\(B'\) を \(B' \oplus B_i\) で置き換える。
• \((A' \oplus A_i) \cup (2^k - 1) \leq K\) ならば、カード \(i\) は必ず選び、カード \(i+1\) 以降はどのように選んでもよいとしたときの最大値を計算して答えの候補とする。その後、カード \(i\) を選ばない場合の最大値を計算するため、\(A', B'\) は変化させない。
• 上記のいずれでもないとき、\(A', A' \oplus A_i\) のうち、二進表記したときに \(2^k\) の位が \(1\) であるものについては、カード \(i+1\) 以降をどのように選んでも表に書かれた整数の排他的論理和を \(K\) 以下にすることはできないので、\(2^k\) の位が \(0\) になるように \(A_i\) を選ぶかどうかを決める。

さて、あとは次のような小問題を解くことができればよいです。

整数 \(B', B_1, \dots, B_m\) が与えられたとき、\(B_1, \dots, B_m\) のうちいくつかを選び、\(B'\) とそれらの整数の排他的論理和を最大化する.

\(B_1, \dots, B_m\) に対し、先ほどと同様に行列を考え、行基本変形によって階段行列にします。その後、上の行から順に、\(B', B' \oplus B_i\) のうち大きい方で \(B'\) を置き換えることを繰り返し、最終的な \(B'\) の値が最大値となります。

以上の解法は \(W = \log(\max (A_1, \dots, A_N, B_1, \dots, B_N))\) として \(O(NW + W^3)\) 程度で実装することができます。

実装例 (C++) :