Grudanje

Ο Patrik λατρεύει να μελετά τις λέξεις της αγγλικής γλώσσας. Λατρεύει ιδιαίτερα τις λέξεις που περιέχουν ακριβώς ~N~ γράμματα. Όταν βλέπει μια τέτοια λέξη, αρχίζει αμέσως να παρατηρεί τις ~Q~ από όλες τις υπολέξεις της και για καθεμία από αυτές τις υπολέξεις καθορίζει εάν όλα τα γράμματά της είναι διακριτά. Αν αυτό ισχύει για καθεμία από τις υπολέξεις ~Q~, τότε θεωρεί ότι η αρχική λέξη είναι τέλεια.

Ο Krešimir δεν του αρέσει να μελετά αγγλικές λέξεις, του αρέσει να πετάει χιονόμπαλες στον Patrik. Ένα κρύο, χειμωνιάτικο πρωινό, περπατούσε στην πόλη κουβαλώντας ακριβώς ~N~ χιονόμπαλες και έπεσε πάνω στον Πάτρικ που παρατηρούσε μια γιγάντια λέξη με γράμματα ~N~ που ήταν γραμμένη στον τοίχο από κάποιους χούλιγκαν. Τι σύμπτωση...

Ο Krešimir πέταξε άγρια την πρώτη χιονόμπαλα προς την κατεύθυνση του Πάτρικ, αλλά ο Patrik απέφυγε επιδέξια τη χιονόμπαλα, έτσι χτύπησε και κάλυψε εντελώς το ~p_1~-οστό γράμμα της λέξης στον τοίχο. Με παρόμοιο τρόπο, ο Krešimir απέτυχε να χτυπήσει τον Patrik με τις επόμενες ~(N - 1)~ χιονόμπαλες. Πιο συγκεκριμένα, η i-οστή χιονόμπαλα του έχασε τον Patrik και κάλυψε εντελώς το ~p_i~-οστό γράμμα της λέξης σε έναν τοίχο. Είναι αρκετά ενδιαφέρον ότι αφού ο Krešimir πέταξε όλες τις χιονόμπαλες, ολόκληρη η λέξη καλύφθηκε από χιόνι.

Ο Patrik έριξε μια ματιά στην εντελώς καλυμμένη λέξη και κατέληξε στο συμπέρασμα ότι ήταν τέλεια. Ως εκ τούτου, έπρεπε να αλλάξει ελαφρώς τον ορισμό του για μια τέλεια λέξη. Η λέξη είναι τέλεια όταν σε καμία από τις υπολέξεις ~Q~ δεν περιέχει δύο ίσα γράμματα που δεν καλύπτονται από χιόνι. Τώρα θέλει να μάθει μετά από ποια χιονόμπαλα (πιθανώς μηδέν) έγινε τέλεια η λέξη στον τοίχο.

Είσοδος

Η πρώτη γραμμή περιέχει μια λέξη που αποτελείται από ~N\;(1 \le N \le 10^5)~ πεζά γράμματα από το αγγλικό αλφάβητο.

Η δεύτερη γραμμή περιέχει έναν ακέραιο αριθμό ~Q\;(1 \le Q \le 10^5)~ από την περιγραφή της εργασίας.

Το i-οστό των επόμενων ~Q~ γραμμών περιέχει δύο ακέραιους αριθμούς ~a_i~ και ~b_i\;(1 \le a_i \le b_i \le N)~ που δηλώνουν ότι η i-οστή των υπολέξεων ~Q~ από την περιγραφή της εργασίας εκτείνεται από το ~a_i~ έως το ~b_i~ γράμμα της λέξης σε έναν τοίχο.

Η επόμενη γραμμή περιέχει ~N~ διαφορετικούς ακέραιους αριθμούς ~p_i\;(1 \le p_i \le N)~.

Έξοδος

Στη μοναδική γραμμή θα πρέπει να βγάζετε μετά την οποία η χιονόμπαλα (πιθανώς μηδέν) έγινε τέλεια η λέξη στον τοίχο.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 14 πόντων, θα ισχύει ~1 \le N, Q \le 500~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 21 πόντων, θα ισχύει ~1 \le N, Q \le 3000~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 14 βαθμών, η λέξη θα περιέχει μόνο γράμματα "~a~".

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

input

aaaaa
2
1 2
4 5
2 4 1 5 3

output

2

input

abbabaab
3
1 3
4 7
3 5
6 3 5 1 4 2 7 8

output

5

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

Η κατάσταση της λέξης στον τοίχο μετά από κάθε πεταμένη χιονόμπαλα είναι:

abbab*ab
ab*ab*ab
ab*a**ab
*b*a**ab
*b****ab
******ab
*******b
********

input

abcd
1
1 4
1 2 3 4

output

0