Hạo vừa học phép toán xor, với hai số nguyên x và y trả về kết quả bằng cách áp dụng phép toán hoặc loại trừ theo bit (exclusive or). Phép toán xor, ký hiệu là \(\oplus\), so sánh các bit tương ứng của các số \(x\) và \(y\) và đặt bit kết quả tại mỗi vị trí theo quy tắc sau:
- Nếu các bit tại vị trí tương ứng khác nhau (\(0\) và \(1\), hoặc \(1\) và \(0\)), thì bit kết quả là \(1\).
- Nếu các bit giống nhau (\(0\) và \(0\), hoặc \(1\) và \(1\)), thì bit kết quả là \(0\).
Ví dụ, với \(x = 5\) và \(y = 3\), biểu diễn nhị phân là: \(x = 101_2\), \(y = 011_2\). Áp dụng xor cho các bit tương ứng ta được \(x \oplus y = 101_2 \oplus 011_2 = 110_2 = 6\). Nói cách khác, \(5 \oplus 3 = 6\).
Hạo nhận được một mảng n số nguyên \(a_1, a_2, ..., a_n\) và quyết định làm như sau:
- Với mỗi cặp chỉ số \((i, j)\) trong đó \(1 \le i \le j \le n\), anh ấy tính tổng \(a_i + a_j\).
- Bây giờ anh ấy muốn tính kết quả của phép xor của tất cả các tổng thu được.
Giúp Hạo tính kết quả cần tìm.
Dữ liệu vào
- Trong dòng đầu tiên, có \(n\) \((1 \le n \le 5 \times 10^5)\), độ dài của mảng.
- Trong dòng thứ hai, có \(n\) số \(a_1, a_2, ..., a_n\) \((0 \le a_i \lt 2^{30})\) như được mô tả trong đề bài.
Dữ liệu ra
- Trong dòng duy nhất, in ra kết quả cần tìm.
Chấm điểm
Subtask | Điểm | Ràng buộc |
---|---|---|
1 | 7 | \(n \le 2000\) |
2 | 17 | \(a_i \lt 2^{10}\) với mọi \(i\) |
3 | 45 | \(n \le 10^5\) |
4 | 21 | Không có ràng buộc bổ sung. |
Input 1
3
2 4 5
Output 1
14
Input 2
4
6 7 3 1
Output 2
3
Input 3
7
2 3 5 7 9 11 13
Output 3
6
Giải thích ví dụ thứ nhất: Các tổng là \(2 + 2 = 4, 2 + 4 = 6, 2 + 5 = 7, 4 + 4 = 8, 4 + 5 = 9\), và \(5 + 5 = 10\). Kết quả là \(4 \oplus 6 \oplus 7 \oplus 8 \oplus 9 \oplus 10 = 14\).
Nhận xét