Tổng và XOR

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
jumptozero , duyboyct
Dạng bài
Điểm: 400 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input 
4 5 10

6 3 2 0

5 4 6 12 7
Output 
15

Bình luận