Ogledala

Υπάρχουν ~M~ σύγχρονοι νιπτήρες αριθμημένοι από το ~1~ έως το ~M~ από αριστερά προς τα δεξιά στο γυναικείο δωμάτιο ενός τεράστιου εμπορικού κέντρου.
Αυτήν τη στιγμή, υπάρχουν ~N~ κυρίες στην τουαλέτα (με αριθμό από ~1~ έως ~N~) και έχουν καταλάβει τους νιπτήρες με αριθμούς ~A_1 , A_2,\ldots , A_N~ . Σύντομα θα φτάσουν ~M - N~ ακόμη κυρίες (αριθμημένες από ~N + 1~ έως ~M~ με τη σειρά άφιξης) που θα καταλάβουν όλους τους υπόλοιπους διαθέσιμους νιπτήρες. Οι κυρίες που φτάνουν κυρίως θέλουν την ιδιωτικότητά τους, οπότε η κάθε μία επιλέγει πάντα έναν διαθέσιμο νιπτήρα με την ακόλουθη διαδικασία:

• Πρώτα βρίσκει τη μεγαλύτερη συνεχόμενη σειρά διαθέσιμων νιπτηρίων. Αν υπάρχουν περισσότερες από μία, αυτή επιλέγει την πιο αριστερή.
  
• Μετά από αυτό, καταλαμβάνει τον μεσαίο νιπτήρα στην επιλεγμένη σειρά. Αν η σειρά είναι άρτια, αυτή επιλέγει το αριστερό από τους δύο μεσαίους νιπτήρες.

Είναι ασφαλές να υποθέσουμε ότι καμία από τις κυρίες δεν θα αφήσει τον νιπτήρα στο άμεσο μέλλον.
Γράψτε ένα πρόγραμμα που θα προσδιορίζει, για καθέναν από τους ~Q~ δοσμένους ακέραιους αριθμούς ~B_i~ , τo όνομα του νιπτήρα που θα να καταληφθεί από την κυρία ~B_i~ .

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~M~ , ~N~ και ~Q~ - τον αριθμό των νιπτήρων, τον αρχικό αριθμό των κυριών στην τουαλέτα και τον αριθμό των κυριών για τις οποίες πρέπει να καθορίσετε ποιον νιπτήρα θα χρησιμοποιήσουν.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ ακέραιους αριθμούς χωρισμένους στο διάστημα, ο ~i~-οστός από αυτούς τους αριθμούς είναι ~A_i~ - το όνομα του νιπτήρα που χρησιμοποιεί η κυρία ~i~.
Η τρίτη γραμμή εισόδου περιέχει ~Q~ ακέραιους αριθμούς διαχωρισμένους με διάστημα, ο ~i~-οστός από αυτούς τους αριθμούς είναι ~B_i~ - το όνομα της κυρία; για την οποία θέλουμε να μάθουμε ποιον νιπτήρα θα χρησιμοποιήσει.
Οι πρώτες ~N~ κυρίες στην τουαλέτα δεν έχουν επιλέξει απαραίτητα τους νιπτήρες τους χρησιμοποιώντας τη διαδικασία που περιγράφεται στην εργασία.
Οι πίνακες ~A~ και ~B~ αυξάνονται αυστηρά. Με άλλα λόγια, ισχύει ~1 \le A_1 < A_2 < \ldots < A_N \le M~ και ~1 \le B_1 < B_2 < \ldots < B_Q \le M~ .

Έξοδος

Εκτυπώστε ~Q~ γραμμές. Η γραμμή ~i~ πρέπει να περιέχει το όνομα του νιπτήρα που θα χρησιμοποιήσει η κυρία με όνομα ~B_i~. Σημείωση: Συνιστούμε να χρησιμοποιήσετε έναν ακέραιο τύπο δεδομένων 64 bit (int64 σε Pascal, long long σε C/C++).

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	19	~1 \le M \le 300\,000~
2	22	~1 \le M \le 10^{14},\,B_Q\le 300\,000~
3	59	~ 1 \le M \le 10^{14}~

Σε όλα τα υποπροβλήματα, θα ισχύει ~1 \le Q \le 10^5,\,N \le M~ και ~1 \le N \le 10^5~.

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

input

7 1 4
4
2 3 4 5

output

2
6
1
3

input

10 2 4
2 8
1 3 5 8

output

2
5
6
4

Επεξήγηση του 2ου πραδείγματος:

Οι πρώτες δύο κυρίες καταλαμβάνουν τους νιπτήρες ~2~ και ~8~ (αντίστοιχα). Οι υπόλοιπες κυρίες καταλαμβάνουν τους νιπτήρες ~5,\,3,\,6,\,9,\,1,\,4,\,7~ και ~10~, αντίστοιχα.