Slasticar

Η διοργάνωση διαγωνισμών CS δεν αποδείχτηκε πολύ προσοδοφόρα για τον Mirko, έτσι άνοιξε ένα κατάστημα παγωτού και ζαχαροπλαστείου. Η επιχείρηση άνθιζε μέχρι που, μια μέρα, η υγειονομική επιθεώρηση της Ευρωπαϊκής Ένωσης αποφάσισε να τον επισκεφθεί.

Μια νέα οδηγία καθορίζει απαγορευμένα ~M~ συστατικά που δεν μπορούν να εμφανιστούν στα τρόφιμα ακόμη και σε ίχνη. Κάθε συστατικό έχει έναν αύξοντα αριθμό που αποτελείται από ψηφία από ~0~ έως ~9~. Η δήλωση σε κάθε συσκευασία τροφίμου αναφέρει όλους τους σειριακούς αριθμούς των συστατικών που περιέχονται στο αντίστοιχο τρόφιμο.

Ο Mirko πρέπει να ελέγξει εάν κάποιο από τα προϊόντα του έχει έναν σειριακό αριθμό απαγορευμένου συστατικού που αναγράφεται στη δήλωσή του. Ωστόσο, ο Mirko, όντας ανίκανος και απερίσκεπτος όπως πάντα, αποφάσισε να συνδέσει όλους τους σειριακούς αριθμούς σε έναν μεγάλο αριθμό με μήκος ~N~, πιστεύοντας ότι θα διευκολύνει τη δουλειά του. Έχει δανειστεί ένα ρομπότ από τον φίλο του Slavko. Το ρομπότ είναι προγραμματισμένο να ελέγχει εάν ένας σειριακός αριθμός ~A~ περιέχει έναν άλλο σειριακό αριθμό ~B~ ως υποσυμβολοσειρά. Ας υποδηλώσουμε το μήκος του ~B~ με ~L~. Το ρομπότ πραγματοποιεί την αναζήτηση ως εξής:

• Αρχικά, συγκρίνει το τμήμα του ~A~ από τη θέση 1 στη θέση ~L~, ψηφίο προς ψηφίο, με τα ψηφία του ~B~. Η σύγκριση διακόπτεται όταν βρεθεί ένα διαφορετικό ψηφίο ή όταν τα τμήματα προσδιορίζονται ως ίσα. Εάν τα τμήματα είναι ίσα, η αναζήτηση διακόπτεται και η αντιστοίχιση αναφέρεται.
• Εάν τα τμήματα δεν είναι ίσα, η παραπάνω διαδικασία επαναλαμβάνεται με το τμήμα από 2 έως ~L+1~. Εάν αυτά τα τμήματα δεν είναι ίσα, η αναζήτηση συνεχίζεται με τα τμήματα 3 έως ~L+2~, 4 έως ~L+3~ κ.λπ.
• Εάν το ρομπότ δεν έχει επαρκή αριθμό ψηφίων για να αποκτήσει ένα πλήρες τμήμα μήκους ~L~ (για παράδειγμα, ξεκινώντας από τον χαρακτήρα 5 σε έναν σειριακό αριθμό με μήκος 8, χρειάζεται ένα τμήμα με μήκος 6), θα συμπληρώσει το αριθμός με τα σημάδια "#". Για παράδειγμα, το τμήμα του "563232" από τη θέση 4 στη θέση 10 είναι "232####".
• Εάν το ρομπότ φτάσει στο τέλος του σειριακού αριθμού (έχοντας δοκιμάσει όλα τα "~N~" τμήματα) χωρίς να έχει βρει το ~B~, αναφέρεται η απουσία αντιστοίχισης.

Το ρομπότ χρειάζεται ένα δευτερόλεπτο για κάθε σύγκριση μεταξύ δύο ψηφίων και ο Slavko χρεώνει τον Mirko ένα δολάριο ανά δευτερόλεπτο για τη χρήση του ρομπότ.

Βοηθήστε τον Mirko να καθορίσει πόσα χρήματα θα πρέπει να πληρώσει στον Slavko για την αντιστοίχιση μοτίβων!

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~N\;(1 \leq N \leq 100\,000)~, το μήκος του μεγάλου σειριακού αριθμού.

Η δεύτερη γραμμή εισόδου περιέχει \(Ν\) ψηφία από το ~0~ έως το ~9~, τον μεγάλο σειριακό αριθμό.

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

Κάθε μία από τις ακόλουθες ~M~ σειρές περιέχει έναν μόνο αποκλεισμένο σειριακό αριθμό.

Ένας απαγορευμένος σειριακός αριθμός δεν θα υπερβαίνει τα ~100\,000~ ψηφία σε μήκος.

Το συνολικό μήκος όλων των απαγορευμένων σειριακών αριθμών δεν θα υπερβαίνει τα ~3\,000\,000~ ψηφία.

Έξοδος

Τυπώστε ~M~ ακέραιους αριθμούς, έναν ανά γραμμή. Η γραμμή ~i~ πρέπει να περιέχει το ποσό σε δολάρια που χρειάζεται να πληρώσει ο Mirko στον Slavko για την αναζήτηση του συστατικού σειριακού αριθμού ~i~.

Βαθμολογία

Σε δεδομένα δοκιμής αξίας τουλάχιστον ~20~% των συνολικών πόντων, ισχύουν οι ακόλουθοι περιορισμοί:

• ~1 \leq N \leq 1000~
• ~1 \leq M \leq 500~
• το μήκος ενός απαγορευμένου συστατικού σειριακού αριθμού δεν υπερβαίνει τα ~1000~

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

input

7
1090901
4
87650
0901
109
090

output

7
10
3
4

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

Πρώτος σειριακός αριθμός: το ρομπότ βρίσκει διαφορετικά πρώτα ψηφία για κάθε τμήμα ~-~ συνολικά 7 συγκρίσεις.
Δεύτερος σειριακός αριθμός: δοκιμάζει την πρώτη θέση, βρίσκοντας τη διαφορά αμέσως (1 σύγκριση). Δοκιμάζει τη πρώτη θέση, βρίσκοντας διαφορά στο τέταρτο ψηφίο (4 συγκρίσεις). Δοκιμάζει τρίτη θέση, βρίσκοντας τη διαφορά αμέσως (1 σύγκριση). Δοκιμάζει την τέταρτη θέση, βρίσκοντας ένα ταίριασμα (4 συγκρίσεις). Σύνολο: 10 συγκρίσεις.
Τρίτος σειριακός αριθμός: τα ευρήματα ταιριάζουν αμέσως (3 συγκρίσεις).
Τέταρτος σειριακός αριθμός: βρίσκει ταίριασμα στη δεύτερη θέση (~1 + 3 = 4~ συγκρίσεις).

input

10
5821052680
4
210526
2105
582
105268

output

8
6
3
9

input

3
001
1
11

output

4

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

Το ρομπότ συγκρίνει τον σειριακό αριθμό "11" κατά σειρά με τα τμήματα "00" (1 σύγκριση), "01" (1 σύγκριση) και "1#"" (2 συγκρίσεις). Σύνολο: 4 συγκρίσεις.