Problem description
Jasiu dostał na urodziny ciąg N liczb A1, A2, …, An i zastanawia się teraz, jak bardzo powinien się cieszyć z tego prezentu.
Postanowił, że swoją decyzję podejmie na podstawie wartości XOR wszystkich liczb postaci Ai + Aj dla 1 ≤ i ≤ j ≤ N.
Jak zazwyczaj, Jasiu nie poradził sobie samemu z tym zadaniem i poprosił Cię o pomoc w znalezieniu interesującej go wartości.
Wejście
W pierwszym wierszu wejścia znajduje się pojedyncza liczba całkowita N – długość ciągu Jasia.
W drugim (i ostatnim) wierszu wejścia znajduje się N liczb całkowitych oddzielonych pojedynczymi spacjami – ciąg A1, A2, …, An Jasia.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna znaleźć się pojedyncza liczba całkowita – wartość interesująca Jasia.
Ograniczenia
1 ≤ N ≤ 106, 1 ≤ Ai ≤ 5 ⋅ 108.
Podzadania
| Podzadanie | Warunki | Punkty |
|---|---|---|
| 1 | N ≤ 4 000 | 7 |
| 2 | Ai ≤ 4 000 | 11 |
| 3 | Ai ≤ 106 | 21 |
| 4 | N ≤ 105 | 38 |
| 5 | brak dodatkowych ograniczeń | 23 |
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
A1 + A1 = 3 + 3 = 6 A1 + A2 = 3 + 7 = 10 A1 + A3 = 3 + 10 = 13 A1 + A4 = 3 + 7 = 10 A2 + A2 = 7 + 7 = 14 A2 + A3 = 7 + 10 = 17 A2 + A4 = 7 + 7 = 14 A3 + A3 = 10 + 10 = 20 A3 + A4 = 10 + 7 = 17 A4 + A4 = 7 + 7 = 14 6 ⊕ 10 ⊕ 13 ⊕ 10 ⊕ 14 ⊕ 17 ⊕ 14 ⊕ 20 ⊕ 17 ⊕ 14 = 17 |
| Wejście | Wyjście | |
|
|
| Wejście | Wyjście | |
|
|