secvxor

Se consideră un şir $A$ cu $N$ elemente numere naturale nenule. Pentru fiecare subsecvenţă de forma $A_{i},A_{i+1},A_{i+2},\ldots,A_{j}$ din şirul $A$ (unde $i \lt j$) pentru care cel mai mare divizor comun al numerelor $A_{i}$ şi $A_{j}$ este mai mare decât $1$, se calculează valoarea $A_{i} \oplus A_{i+1} \oplus \ldots \oplus A_{j}$, unde $\oplus$ este operaţia sau exclusiv pe biţi (notată în C/C++ cu ^). Între valorile obţinute pentru fiecare subsecvenţă se efectuează din nou operaţia $\oplus$, obţinând ca rezultat un număr $B$.

Se cere să se determine valoarea lui $B$.

Date de intrare

Pe prima linie a fişierului de intrare se află numărul $N$, iar pe a doua linie elementele şirului $A$.

Date de ieșire

Pe prima linie a fişierului de ieşire se va afişa valoarea numărului $B$.

Restricții

• $1\leq N \leq 100\ 000$
• $1\leq A_{i} \leq 1\ 000\ 000$

  #	Punctaj	Restricții
  1	9	$1\leq N\leq 500$
  2	12	$1\leq N\leq 5\ 000$
  3	15	Elementele şirului $A$ sunt numere pare.
  4	26	Elementele şirului $A$ sunt numere prime.
  5	38	Fără restricții suplimentare

Exemplu

secvxor.in

5
4 7 6 10 21

secvxor.out

1

Explicație

Operaţia $\oplus$ se defineşte astfel: $0 \oplus 0 = 1 \oplus 1 = 0$, $\ \ 0 \oplus 1 = 1 \oplus 0 = 1$, și $\ (2k + \ell) \oplus (2k' + \ell') = 2(k \oplus k') + (\ell \oplus \ell')$ pentru $k, k' \geq 0$ și $0 \leq \ell, \ell' \leq 1$.

De exemplu, pentru numerele $7$ şi $18$ scrierea lor în baza $2$ este $7=111_{2}$, respectiv $18=10010_{2}$. Efectuând operaţia $\oplus$ între aceste numere vom obţine rezultatul $10101_{2}=21$.

Subsecvenţele care satisfac proprietatea din enunţ (adică sunt de lungime cel puţin 2, iar elementele de la începutul şi sfârşitul subsecvenţei au cel mai mare divizor comun mai mare decât $1$) sunt: $(4,7,6)$, $(4,7,6,10)$, $(7,6,10,21)$, $(6,10)$, $(6,10,21)$. Efectuând operaţia $\oplus$ între elementele fiecărei subsecvenţe obţinem valorile $5,15,30,12$, respectiv $25$. Efectuând operaţia $\oplus$ între aceste valori obţinem valoarea lui $B=1$.