Helping Fill Bates

Όλοι γνωρίζουν τον Fill Bates, αλλά φαντάζομαι ότι λιγότεροι γνωρίζουν ότι ήταν ξακουστός στα λυκειακά του χρόνια για έναν διαφορετικό λόγο. Σας παραθέτω τις ακριβείς γραμμές από μία από τις σύντομες βιογραφίες του:

Τώρα πρόκειται να τον βοηθήσετε για έναν εντελώς διαφορετικό σκοπό. Η εταιρεία του έχει ξεκινήσει ένα πρόγραμμα αναζήτησης ταλέντων στην QSA. Έχει ~52~ πολιτείες (τις αρχικές ~50~ πολιτείες συν τις δύο πρόσφατες προβληματικές προσθήκες ~Oraq~ και ~Malistan~). Στους υποψηφίους από τις ~52~ πολιτείες δίνονται πολιτειακές ταυτότητες και ένας σειριακός αριθμός (ο σειριακός αριθμός είναι μοναδικός). Οι ταυτότητες για τις ~52~ πολιτείες είναι οι ~52~ χαρακτήρες ASCII ~A..Z~ και ~a..z~. Η διαδικασία αναζήτησης των ταλέντων είναι λίγο περίεργη. Το πολύ ~1~ εκατομμύριο υποψήφιοι στέκονται σε μια σειρά κατά αύξοντα σειριακό αριθμό (ξεκινώντας με το ~0~ και στη συνέχεια ~1~, ~2~, ~3~ κ.λπ.) με μια πινακίδα που δείχνει μόνο την πολιτειακή τους ταυτότητα (άλλωστε ποιος θέλει να προσλάβει υπαλλήλους από το Οράκ και το Μαλιστάν). Στη συνέχεια ο κ. Fill Gates γράφει μια ακολουθία χαρακτήρων (μόνο αλφαβητικούς). Αν οι υποψήφιοι βρεθούν σε αυτή τη σειρά με αύξοντες σειριακούς αριθμούς (κάποιοι υποψήφιοι μπορεί να παραλειφθούν για αυτό το σκοπό), τότε αυτοί οι υποψήφιοι λαμβάνονται. Διαφορετικά, δίνεται κατάλληλο μήνυμα.

Είσοδος

Το αρχείο εισόδου περιέχει μόνο ένα σύνολο δεδομένων εισόδου.

Η πρώτη γραμμή του αρχείου εισόδου περιέχει μια συμβολοσειρά S που αποτελείται μόνο από αλφαβητικούς χαρακτήρες. Το μήκος αυτής της συμβολοσειράς είναι το πολύ ~1\;000\;000~.

Η επόµενη γραµµή περιέχει έναν ακέραιο αριθµό ~Q\;(0 < Q < 3501)~ που δηλώνει τον αριθμό των ερωτημάτων. Κάθε μία από τις επόμενες γραμμές ~Q~ περιέχει μια σειρά SS μήκους μικρότερου από ~101~. Αυτές οι συμβολοσειρές είναι οι συμβολοσειρές που γράφτηκαν από τον Fill Bates.

Έξοδος

Για κάθε ερώτημα θα πρέπει να εξάγετε μία γραμμή. Εάν οι υποψήφιοι δεν βρεθούν με τη σειρά που γράφει ο Fill Bates, τότε θα πρέπει να εξάγετε τη συμβολοσειρά '~Not\;matched~' (χωρίς τα εισαγωγικά), διαφορετικά θα πρέπει να εκτυπώσετε '~Matched~' (Σημειώστε ότι μετά το 'Matched' εκτυπώνεται ένα κενό διάστημα) και στη συνέχεια τον σειριακό αριθμό του πρώτου υποψηφίου στην υποακολουθία και τον σειριακό αριθμό του τελευταίου υποψηφίου της υποακολουθίας. Αυτοί οι δύο ακέραιοι αριθμοί θα πρέπει να χωρίζονται με ένα κενό διάστημα. Εάν υπάρχουν περισσότερες από μία τέτοιες υποακολουθίες, τότε επιλέξτε εκείνη που έχει τον μικρότερο αρχικό σειριακό αριθμό. Εάν υπάρχει ισοπαλία, επιλέξτε αυτή με τον μικρότερο τελικό σειριακό αριθμό.

Παράδειγμα

input

aaaaaaaaaaaaaabbbbbbbbbdddddddddddccccccccccccc
3
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaabbbbbbbbbbbc
abccc

output

Not matched
Not matched
Matched 0 36