Zadanie

Hrozná správa

Počet bodov: 45

Samkovi sa páči jedno milé dievča. Ona ho veľmi dobre pozná, takže po tom čo ju Samko pozval na rande a ona ho odmietla mu dala informatickú úlohu - nech ju vyrieši a nebude taký smutný. Samo je však zdrvený a vôbec sa na riešenie úlohy nevie sústrediť. Pomôžte mu.

Úloha

Samozrejme, nejaké jedno odmietnutie nemôže takého skúseného programátora úplne položiť, takže aj v tejto kritickej situácii sa mu podarilo s úlohou trochu pohnúť. Zredukoval ju do nasledovného znenia. Máme pole čísel a niekoľko dotazov. Každý dotaz bude označovať nejaký interval daného poľa a pre každý takýto interval máme vykonať nasledujúci algoritmus.

1. Z intervalu vytvoríme všetky neprázdne podpostupnosti (povedzme že ich je \(P\))
2. Pre každú podpostupnosť jej hodnoty utriedime a následne vypočítame ich XOR (teda z \(P\) podpostupnosti získame \(P\) hodnôt)
3. Na výslednom zozname zopakujeme predchádzajúci krok, teda daných \(P\) hodnôt utriedime a vypočítame ich XOR - toto je výsledok Cieľom úlohy je neprekvapivo vypísať výsledok pre každý dotaz.

Po tom čo vám toto Samo vysvetlil odišiel do svojej izby určite neplakať. Skúste úlohu vyriešiť pred tým ako sa vráti, máte na to asi zopár hodín.

Vstupu

Na prvom riadku vstupu dostanete dve čísla \(1 \le N \le 10^5\) a \(0 \le Q \le 10^5\) - dĺžka pola a počet dotazov. Na druhom riadku bude \(N\) medzerou oddelených celých čísel \(0 \le a_i \le 10^9+7\). Zvyšok vstupu tvorí \(Q\) riadkov, na každom riadku budú dve čísla \(1 \le l_i \le r_i \le N\) udávajúce uzavretý interval pre \(i\)-ty dotaz.

Výstup

Vypíšte \(Q\) riadkov, na \(i\)-tom riadku výsledok \(i\)-teho dotazu.

Obmedzenia

Vstupy budú rozdelené do niekoľkých sád. Čiastočné body sa dajú získať aj za neoptimálne riešenia.

Príklad

Input:

6 2
1 2 3 4 4 4
1 1
4 6

Output:

1
0

V prvom dotaze bude jedinou neprázdnou podpostupnosťou postupnosť \((1)\), ktorej XOR bude 1

V druhom dotaze budeme mať 7 neprázdnych podpostupností \((4),(4),(4),(4,4),(4,4),(4,4),(4,4,4)\). Sú už utriedené a ich XORy sú \(4,4,4,0,0,0,4\). Keď toto utriedime získame \(0,0,0,4,4,4,4\) čoho XOR je \(0\)