Divljak

Σήμερα, υπάρχουν πολλοί ασυνήθιστοι άνθρωποι. Δεν θα υπεισέλθουμε σε λεπτομέρειες, αλλά αντίθετα θα επικεντρωθούμε σε έναν συγκεκριμένο τύπο, για εμάς προσωπικά τους πιο ενδιαφέροντες ανθρώπους. Φυσικά, μιλάμε για βάρβαρους!

Υπάρχουν πολλοί βάρβαροι, αλλά μόνο λίγοι από αυτούς είναι πραγματικά σημαντικοί. Αυτή η ιστορία έχει ~N~ σημαντικούς βάρβαρους, που συμβολίζονται με ακέραιους αριθμούς από το 1 έως το ~N~. Καθένας από αυτούς έχει τη δική του πέτρινη ταμπλέτα με τη λέξη του γραμμένη πάνω του, που αποτελείται μόνο από πεζά γράμματα του αγγλικού αλφαβήτου.

Οι βάρβαροι μας παίζουν ένα ενδιαφέρον παιχνίδι με τον καλό τους φίλο Ταρζάν.

Το παιχνίδι παίζεται σε ~Q~ γύρους. Υπάρχουν δύο τύποι γύρων και καθένας καθορίζεται από τον Ταρζάν:
  1ος τύπος: Ο Ταρζάν δείχνει τη λέξη ~P~ στους βαρβάρους.
  2ος τύπος: Ο Ταρζάν κάνει στον βάρβαρο, που συμβολίζεται με ~S~, την ακόλουθη ερώτηση: "Από όλες τις λέξεις που
       σας έχω δείξει μέχρι τώρα, πόσες από αυτές είναι τέτοιες που η λέξη στην πέτρινη πλάκα σας είναι η
       διαδοχική υποχορδή τους;"

Δεδομένου του γεγονότος ότι οι βάρβαροι αγριεύουν πολύ και δεν είναι πραγματικά σε θέση να δώσουν προσοχή και να παρακολουθήσουν τι συμβαίνει στο παιχνίδι, χρειάζονται τη βοήθειά σας. Βοηθήστε τους βάρβαρους να απαντήσουν σωστά σε κάθε ερώτηση του Ταρζάν.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \leq N \leq 10^5 )~, τον αριθμό των βαρβάρων.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει μια λέξη που αποτελείται μόνο από πεζά γράμματα του αγγλικού αλφαβήτου, η ~i~-οστή λέξη αντιστοιχεί στη λέξη στην πέτρινη πλάκα του βαρβάρου που συμβολίζεται με ~i~.

Μετά από αυτό, ακολουθεί ο ακέραιος ~Q\;(1 \leq Q \leq 10^5 )~, ο αριθμός των γύρων στο παιχνίδι.

Οι ακόλουθες ~Q~ γραμμές περιγράφουν τον γύρο του παιχνιδιού, η ~i~-οστή γραμμή περιγράφει τον ~i~-οστό γύρο του παιχνιδιού.
Κάθε γραμμή θα περιέχει τον ακέραιο αριθμό ~O~. Στην περίπτωση που το ~O~ είναι ίσο με 1, υποδηλώνει τον πρώτο τύπο γύρου και η εμφανιζόμενη λέξη ~P~ ακολουθεί στην ίδια γραμμή, που αποτελείται μόνο από πεζά γράμματα του αγγλικού αλφαβήτου.

Στην περίπτωση που το ~O~ είναι ίσο με 2, υποδηλώνει τον δεύτερο τύπο γύρου και ο αριθμός ~S\;(1 \leq S \leq N )~ ακολουθεί στην ίδια γραμμή, η ετικέτα του βαρβάρου που ο Ταρζάν έκανε την ερώτηση.

Το συνολικό μήκος όλων των λέξεων που είναι γραμμένες στις πέτρινες πλάκες των βαρβάρων δεν θα υπερβαίνει τις ~2 \times 10^6~.
Το συνολικό μήκος όλων των λέξεων που δείχνει ο Ταρζάν στους βάρβαρους δεν θα υπερβαίνει τις ~2 \times 10^6~ .

Έξοδος

Για κάθε γύρο διαφορετικής μορφής, τυπώνετε μια γραμμή. Η ~i~-οστή γραμμή πρέπει να περιέχει τη σωστή απάντηση στην ερώτηση του Ταρζάν στον ~i~-οστό γύρο του τύπου 2.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~50~% των συνολικών πόντων, θα έχει ~N \leq 20\,000~

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

input

3
a
bc
abc
3
1 abca
2 1
2 3

output

1
1

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

Η μόνη λέξη που έχει δείξει ο Ταρζάν είναι το ~abca~. Η απάντηση στην πρώτη ερώτηση είναι, φυσικά, 1 επειδή η λέξη ~a~ είναι υποσυμβολοσειρά της λέξης ~abca~. Η απάντηση στη δεύτερη ερώτηση είναι επίσης 1 επειδή η λέξη ~abc~ είναι υποσυμβολοσειρά της λέξης ~abca~.

input

7
abba
bbaa
b
bbaa
abba
a
ba
7
1 aaabbabbaab
2 7
1 baabaaa
1 aabbbab
2 3
1 aabba
2 3

output

1
3
4