Ozljeda

Λόγω της ξέφρενης χρήσης της ρακέτας για να σκοτώνει τις μύγες, ο Marin έχει υποστεί σοβαρό σωματικό τραυματισμό που είναι γνωστός στην ιατρική κοινότητα ως epicondylitis lateralis humeri (πλευρική βραχιόνια επικονδυλίτιδα). Η γιαγιά του τον συμβούλευσε να αλείψει ρακί πάνω στον τραυματισμό, ο γιατρός έχει συνταγογραφήσει ένα ισχυρό παυσίπονο, αλλά ο Μάριν αγνόησε κάθε συμβουλή και αποφάσισε να αναζητήσει την απάντηση σε ακέραιες ακολουθίες. Ανακάλυψε μια ακολουθία ακεραίων αριθμών που δεν είχε ανακαλυφθεί στο παρελθόν και την ονόμασε ακολουθία xorbonacci. Το n-οστό στοιχείο της ακολουθίας συμβολίζεται με ~x_n~ . Η ακολουθία ορίζεται αναδρομικά με τον ακόλουθο τρόπο:
     ~x_1\;=\;a_1~,
     ~x_2\;=\;a_2~,
        ...
     ~x_k\;=\;a_k~,
     ~x_n\;=\;x_{n-1}\;\oplus\;x_{n-2}\;oplus\;...\;\oplus\;x_{n-k},\;n\;>\;k~
Λόγω ενός λόγου που γνώριζε μόνο ο Marin, αποφάσισε ότι όλες οι στεναχώριες του θα εξαφανιστούν αν απαντήσετε στα ερωτήματά του ~Q~ που ορίζονται με τους αριθμούς ~l~ και ~r~. Η απάντηση στο ερώτημα αντιπροσωπεύεται με την τιμή

~x_l\;\oplus\;x_{l+1}\;oplus\;...\;\oplus\;x_{r-1}\;\oplus\;x_r~

Βοηθήστε τον Marin και απαντήστε στις ερωτήσεις του.

Σημείωση: Η λειτουργία ~\oplus~ είναι η λειτουργία του δυαδικού XOR.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~K\;(1 \leq K \leq 100\;000)~.
Η ακόλουθη γραμμή περιέχει ~K~ ακέραιους που αντιπροσωπεύουν τα πρώτα ~K~ στοιχεία στην ακολουθία xorbonacci.
Όλοι οι αριθμοί είναι μικρότεροι από το ~10^{18}~.
Η ακόλουθη γραμμή περιέχει τον ακέραιο αριθμό ~Q\;(1 \leq Q \leq 10^6\;)~.
Η i-οστή από τις ακόλουθες ~Q~ γραμμές περιέχει δύο ακέραιους αριθμούς ~l_i~ και ~r_i\;(1 \leq l_i \leq r_i \leq 10^{18})~, που αντιπροσωπεύουν το i-οστό ερώτημα του Marin.

Έξοδος

Κάθε μία από τις ακόλουθες ~Q~ γραμμές εξόδου πρέπει να περιέχει τις απαντήσεις στα ερωτήματα του Marin, με τη σειρά να είναι ίδια με αυτήν της εισόδου.

Παραδείγματα

input

4
1 3 5 7
3
2 2
2 5
1 5

output

3
1
0

input

5
3 3 4 3 2
4
1 2
1 3
5 6
7 9

output

0
4
7
4