Rule of Three

Ένας κανόνας αντικατάστασης περιγράφει πώς να πάρετε μια ακολουθία συμβόλων και να τη μετατρέψετε σε μια διαφορετική ακολουθία συμβόλων. Για παράδειγμα, το ABA ~\to~ BBB, είναι ένας κανόνας αντικατάστασης που σημαίνει ότι ABA μπορεί να αντικατασταθεί με BBB. Χρησιμοποιώντας αυτόν τον κανόνα, η ακολουθία AABAA θα μετατραπεί στην ακολουθία ακολουθία ABBBA (τα σύμβολα που αντικαθίστανται είναι σε έντονη γραφή).

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

Για παράδειγμα, αν οι τρεις κανόνες αντικατάστασης ήταν:

1. AA ~\to~ AB
2. ΑΒ ~\to~ ΒΒ
3. Β ~\to~ ΑΑ

θα μπορούσαμε να μετατρέψουμε την ακολουθία AB σε ΑΑΑΒ σε ~4~ βήματα, με τις ακόλουθες αντικαταστάσεις:

AB ~\to~ BB ~\to~ AAB ~\to~ AAAA ~\to~ AAAB,

όπου τα σύμβολα που πρέπει να αντικατασταθούν εμφανίζονται με έντονη γραφή. Πιο συγκεκριμένα, από την αρχική ακολουθία AB, αντικαθιστούμε με τον κανόνα ~2~ ξεκινώντας από τη θέση ~1~, για να προκύψει το BB. Από το BB, αντικαθιστούμε με τον κανόνα ~3~, ξεκινώντας από τη θέση ~1~, για να προκύψει το αποτέλεσμα AAB. Από το AAB, αντικαθιστούμε με τον κανόνα ~3~, ξεκινώντας από τη θέση ~3~, για να προκύψει το αποτέλεσμα αποτέλεσμα AAAA. Από το AAAA, αντικαθιστούμε με τον κανόνα ~1~, ξεκινώντας από τη θέση ~3~, για να προκύψει το AAAB, το οποίο είναι η τελική ακολουθία.

Είσοδος

Οι τρεις πρώτες γραμμές θα περιέχουν τους κανόνες αντικατάστασης. Κάθε κανόνας αντικατάστασης θα είναι μια ακολουθία από A και B, ακολουθούμενη από ένα κενό και στη συνέχεια από μια άλλη ακολουθία από A και B. Και οι δύο ακολουθίες θα έχουν από ένα έως πέντε σύμβολα.

Η επόµενη γραµµή περιέχει τρεις τιµές χωρισµένες µε κενό, ~S~, ~I~ και ~F~ . Η τιμή ~S\;(1 \le S \le 15)~ είναι ένα ακέραιος αριθμός που δηλώνει τον αριθμό των βημάτων που πρέπει να εφαρμοστούν, και οι τιμές ~I~ (η αρχική ακολουθία) και ~F~ (η τελική ακολουθία) είναι ακολουθίες από ~A~ και ~B~, όπου υπάρχουν τουλάχιστον ένα και το πολύ ~5~ σύμβολα στην ~I~ και τουλάχιστον ένα και το πολύ ~50~ σύμβολα στην ~F~ .

Για ~7~ από τους ~15~ διαθέσιμους βαθμούς, ~S \le 6~.

Για επιπλέον ~7~ από τους ~15~ διαθέσιμους βαθμούς, ~S \le 12~.

Έξοδος

Η έξοδος θα έχει μήκος ~S~ γραμμές και θα περιγράφει τις αντικαταστάσεις με τη σειρά. Η γραμμή ~i~ της εξόδου θα περιέχει τρεις τιμές, ~R_{i}~, ~P_{i}~ και ~W_{i}~, χωρισμένες με κενό διάστημα:

• ~R_{i}~ είναι ο αριθμός του κανόνα αντικατάστασης (~1~, ~2~ ή ~3~) που θα χρησιμοποιηθεί.
• ~P_{i}~ είναι ο δείκτης της αρχικής θέσης όπου θα εφαρμοστεί ο κανόνας αντικατάστασης στην ακολουθία. Σημειώστε ότι η συμβολοσειρά έχει βάση δείκτη ~1~ (δηλαδή, ο πρώτος χαρακτήρας της συμβολοσειράς έχει δείκτη ~1~).
• ~W_{i}~ είναι η ακολουθία που προκύπτει από αυτή την αντικατάσταση. Συγκεκριμένα, ~W_{i}~ είναι η ακολουθία συμβόλων που προκύπτει από την εφαρμογή του κανόνα αντικατάστασης ~R_{i}~ ξεκινώντας από τη θέση ~P_{i}~ από την προηγούμενη ακολουθία συμβόλων, ~W_{i-1}~, όπου ορίζουμε την αρχική ακολουθία ~I~ ως ~W_{0}~. Σημειώστε ότι ~W_{S} = F~ , είναι η τελική ακολουθία.

Θα υπάρχει πάντα τουλάχιστον μία ακολουθία ~S~ αντικαταστάσεων που θα μετατρέψει την ~I~ σε ~F~ . Εάν υπάρχουν περισσότερες από μία πιθανές ακολουθίες αντικαταστάσεων, οποιαδήποτε έγκυρη ακολουθία θα είναι αποδεκτή.

Παράδειγμα

input

AA AB
AB BB
B AA
4 AB AAAB

output

2 1 BB
3 2 AAB
3 3 AAAA
1 3 AAAB

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

Αυτό είναι το παράδειγμα που αναφέρθηκε στην περιγραφή του προβλήματος. Παρατηρήστε ότι η ακόλουθη είναι μια από τις πιθανές έγκυρες ακολουθίες αντικατάστασης:

2 1 BB
3 2 BAA
1 2 BAB
3 1 AAAB

Συγκεκριμένα, δείχνοντας τις αντικαταστάσεις με έντονη γραφή, έχουμε AB ~\to~ BB ~\to~ BAA ~\to~ BAB ~\to~ AAAB.