Specijacija

Σας δίνεται ένας θετικός ακέραιος n και μια ακολουθία $a_1,a_2,\dots ,a_n$ από θετικούς ακέραιους αριθμούς, τέτοιοι ώστε: $\frac{i(i-1)}{2}<a_i\le \frac{i(i+1)}{2}$.

Η ακολουθία παραμετροποιεί ένα δέντρο με $\frac{(n+1)(n+2)}{2}$ κορυφές, που αποτελούνται από $n+1$ επίπεδα με $1,2,\dots ,n+1$ κορυφές, με τον ακόλουθο τρόπο:

Το δέντρο παραμετροποιείται με $a=(1,2,6)$.

Το i-οστό επίπεδο έχει κορυφές $\frac{i(i-1)}{2}+1,\dots ,\frac{i(i+1)}{2}$. Η κορυφή $a_i$ έχει δύο παιδιά, και οι υπόλοιπες κορυφές στο επίπεδο έχουν ένα παιδί η καθεμία.

Θέλουμε να απαντήσουμε σε $q$ ερωτήματα της μορφής "Ποιός είναι ο μεγαλύτερος κοινός πρόγονος των $x$ και $y$;", δηλαδή η κορυφή με τη μεγαλύτερη τιμή που είναι πρόγονος και του $x$ και του $y$.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς $n,q$ και $t(1\le n,q\le 200000,t\in 0,1)$, τον αριθμό των παραμέτρων, τον αριθμό των ερωτημάτων και μια τιμή που θα χρησιμοποιηθεί για τον προσδιορισμό των τιμών των κορυφών στα ερωτήματα.

Η δεύτερη γραμμή περιέχει μια ακολουθία n ακέραιων αριθμών $a_i(\frac{i(i-1)}{2}<a_i\le \frac{i(i+1)}{2})$, που παραμετροποιούν το δέντρο.

Η i-οστή από τις παρακάτω $q$ γραμμές περιέχει δύο ακέραιους $x_i$ και $y_i(1\le \widetilde{x_i},\widetilde{y_i}\le \frac{(n+1)(n+2)}{2})$, οι οποίοι θα χρησιμοποιηθούν για τον προσδιορισμό των τιμών των κορυφών στα ερωτήματα.

Έστω $z_i$ η απάντηση στο i-οστό ερώτημα και έστω $z_0=0$. Οι τιμές, στο i-οστό ερώτημα, $x_i$ και $y_i$ είναι:

$x_i=((\widetilde{x_i}-1+t\cdot z_{i-1})mod\frac{(n+1)(n+2)}{2})+1$,
$y_i=((\widetilde{y_i}-1+t\cdot z_{i-1})mod\frac{(n+1)(n+2)}{2})+1$,
όπου mod είναι το υπόλοιπο της ακέραιας διαίρεσης αριθμού.

Παρατήρηση: Σημειώστε ότι αν $t=0$, ισχύει $x_i=\widetilde{x_i}$ και $y_i=\widetilde{y_i}$, επομένως όλα τα ερωτήματα είναι γνωστά από την είσοδο. Αν $t=1$, τα ερωτήματα δεν είναι γνωστά εκ των προτέρων, αλλά καθορίζονται χρησιμοποιώντας απαντήσεις προηγούμενων ερωτημάτων.

Έξοδος

Περιλαμβάνει $q$ γραμμές. Στην $i$-οστή γραμμή τυπώνουμε τον μεγαλύτερο κοινό πρόγονο των $x_i$ και $y_i$.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	$q=1,t=0$
2	10	$n\le 1000,t=0$
3	30	$t=0$
4	60	$t=1$

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

input

3 5 0
1 2 6
7 10
8 5
6 2
9 10
2 3

output

1
5
1
6
1

---

input

3 5 1
1 2 6
7 10
8 5
6 2
9 10
2 3

output

1
6
2
1
1

Επεξήγηση των παραδειγμάτων:

Το δέντρο και από τα δύο παραδείγματα φαίνεται στο αρχικό σχήμα.

Οι τιμές των κορυφών των ερωτημάτων στο δεύτερο παράδειγμα είναι:
$x_1=7,y_1=10$,
$x_2=9,y_2=6$,
$x_3=2,y_3=8$,
$x_4=1,y_4=2$,
$x_5=3,y_5=4$.

---