Cho dãy \(a\) gồm \(n\) phần tử và dãy \(b\) gồm \(m\) phần tử và một số nguyên dương \(k\).

Với mỗi cặp \((i, j)\) sao cho \(1 ≤ i ≤ n, 1 ≤ j ≤ m\) người ta viết các giá trị \(a_i + b_j\) ra một mảnh giấy rồi sắp xếp lại theo thứ tự không giảm. Sau đó, người ta tính tổng XOR \(k\) phần tử đầu tiên trên mảnh giấy.

Hãy cho biết kết quả của phép tính tổng XOR trên.

Input

• Dòng đầu tiên gồm \(3\) số nguyên dương \(n, m, k (n, m ≤ 10 ^ 5, k ≤ n \times m)\). Dòng thứ hai gồm \(n\) số nguyên không âm \(a_1, a_2, ..., a_n. (a_i < 2 ^ {30})\). Dòng thứ ba gồm \(m\) số nguyên không âm \(b_1, b_2, ..., b_m. (b_i < 2 ^ {30})\).

Output

• In ra tổng XOR cần tìm.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, m \le 1000.\)

• Subtask \(2\) (\(25\%\) số điểm): \(k \le 10 ^ 5.\)

• Subtask \(3\) (\(25\%\) số điểm): \(a_i, b_i < 2 ^ {10}.\)

• Subtask \(4\) (\(25\%\) số điểm): \(k = n \times m.\)

Example

4 5 10

6 3 2 0

5 4 6 12 7

15