Kriptogram

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

Είσοδος

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

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει το ευρετήριο στο κρυπτογραφημένο μήνυμα της πρώτης λέξης στην πρώτη εμφάνιση της δεδομένης αρχικής πρότασης μηνύματος.
Λύση πάντα θα υπάρχει.

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

input

a a a b c d a b c $
x y $

output

3

input

xyz abc abc xyz $
abc abc $

output

2

input

a b c x c z z a b c $
prvi dr prvi tr tr x $

output

3