XOR Submatrix

Time limit2sMemory limit512 MB

Summary
Build the N by M matrix with A[i][j] = V[i] xor U[j] and find the submatrix whose elementwise xor is maximal.
Level

Hard8 of 10

Topics
Bit manipulation, Trie, Prefix sum, Math
Solved
No attempts yet

Problem

Using an array V of size N and an array U of size M, we can build an N×M matrix A where Aij = Vi xor Uj.

Write a program that finds the submatrix of A whose elements xor to the largest value.

Input

The first line gives the array sizes N and M. The second line gives V1, V2, ..., VN, and the third line gives U1, U2, ..., UM.

Output

Print the largest value obtained by xorring all elements of a submatrix of A.

Constraints

  • 1 ≤ N, M ≤ 1,000
  • 0 ≤ Vi, Uj < 229

Examples3

  1. Example 1

    Input
    3 4
5 3 1
2 1 2 4
    Expected output
    7

  2. Example 2

    Input
    3 3
10 12 4
5 10 9
    Expected output
    15

  3. Example 3

    Input
    3 3
1 2 1
4 2 8
    Expected output
    15