Specijacija

Σας δίνεται ένας θετικός ακέραιος n και μια ακολουθία ~a_1,\;a_2,\;\ldots,\;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,\;\ldots,\;n+1~ κορυφές, με τον ακόλουθο τρόπο:

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

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

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

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~n, q~ και \(t\;(1 \le n, q \le 200\,000,\;t∈{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~.

---