配点 : $400$ 点

問題文

非負整数のみからなる長さ $N$ の数列 $a,b$ が与えられます。$a,b$ の $i$ 番目の要素はそれぞれ $a_i, b_i$ です。

非負整数 $x$ が以下の条件を満たすとき、$x$ を よい数 と呼びます。

• 条件：$b$ を並べ替えて、$1 \leq i \leq N$ を満たすどの整数 $i$ についても $a_i \text{ XOR } b_i = x$ が成立するようにすることができる。ここで、$\text{XOR }$ はビットごとの排他的論理和である。

よい数を小さい方からすべて列挙してください。

制約

• 与えられる入力は全て整数
• $1 \leq N \leq 2000$
• $0 \leq a_i, b_i < 2^{30}$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $\cdots$ $a_N$

$b_1$ $\cdots$ $b_N$

出力

$1$ 行目によい数の個数 $K$ を出力せよ。 続けて $K$ 行出力せよ。続く $K$ 行の $i$ 行目には小さい方から $i$ 番目のよい数を出力せよ。

3
1 2 3
6 4 7

1
5

• $b$ を $(4, 7, 6)$ と並び替えたとき、$a_1 \text{ XOR } b_1 = a_2 \text{ XOR } b_2 = a_3 \text{ XOR } b_3 = 5$ となるため、$5$ はよい数です。他によい数はありません。

2
0 1
0 2

0

24
14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481
805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010

8
107543995
129376201
139205201
160626723
312334911
323172429
481902037
493346727