Piramida

Ο Zoran και ο Tomislav δεν έχουν τίποτα σημαντικό να κάνουν, έτσι περνούν τις μέρες τους κάνοντας διάφορες δραστηριότητες. Σήμερα, έχτισαν μια πυραμίδα ύψους ~N~ στον πίσω κήπο και έγραψαν την αγαπημένη τους λέξη πάνω της, επαναλαμβάνοντας την από γραμμή σε γραμμή και αλλάζοντας κατεύθυνση, όπως φαίνεται στην εικόνα.

Ο Tomislav έχει πλέον επιλέξει ~K~ γραμμές της πυραμίδας, σημειωμένες με ~a_i~, και έχει επιλέξει ένα γράμμα ~c_i~ για κάθε γραμμή. Έπειτα έκανε στον Zoran ~K~ δύσκολες ερωτήσεις: "Πόσες φορές εμφανίζεται το γράμμα ~c_i~ στη σειρά ~a_i~;"

Είσαι σύμβουλος του Zoran. Γράψτε ένα πρόγραμμα που, για το δεδομένο ύψος της πυραμίδας και την αγαπημένη τους λέξη, θα απαντήσει στις ερωτήσεις του Tomislav.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N\;(1 \le N \le 10^{18})~ .

Η δεύτερη γραμμή εισόδου περιέχει μια λέξη που αποτελείται μόνο από κεφαλαία γράμματα του αγγλικού αλφαβήτου. Το μήκος της λέξης δεν θα υπερβαίνει το ~10^6~.

Η τρίτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~K\;(1 \le K \le 50\,000)~, τον αριθμό των γραμμών που έχει επιλέξει ο Tomislav.

Κάθε μία από τις ακόλουθες γραμμές ~K~ περιέχει το ζεύγος ~a_i ,\;c_i\;(1 \le a_i \le N ,\;c_i~ κεφαλαίο γράμμα του αγγλικού αλφαβήτου) που αντιπροσωπεύουν τις ερωτήσεις του Tomislav.

Έξοδος

Τυπώστε ~K~ γραμμές. Η ~i~-οστή γραμμή πρέπει να περιέχει έναν μόνο ακέραιο αριθμό ~-~ τον αριθμό των εμφανίσεων του γράμματος ~c_i~ στη σειρά ~a_i~ .

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50% των συνολικών πόντων, το ~N~ δεν θα υπερβαίνει το ~1000~ . Σε περιπτώσεις δοκιμής αξίας 70% των συνολικών πόντων, το μήκος της συμβολοσειράς δεν θα υπερβαίνει το ~10^5~ .

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

input

6
JANJETINA
5
1 J
1 A
6 N
6 I
5 E

output

1
0
2
1
1

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

Δείτε την παραπάνω.

input

5
A
5
1 A
2 A
3 A
4 A
5 B

output

1
2
3
4
0

input

3
AB
3
2 A
2 B
3 B

output

1
1
2