输入描述:

输入共四行。

前三行每行代表一种操作规则，序号分别为1 2 3，每行包含两个只包含字符A和B的字符串s和t，代表该规则可以将s替换成t。

第四行包含三个元素：一个数字a，两个随机字符串S和T，a代表操作次数，S代表起始串，T代表目标串。

输出描述:

输出a行，每行包括三个元素，中间用空格隔开，代表操作步骤：

数字x和数字y，字符串P，x代表选择的操作规则(1/2/3)，y代表在串中的操作位置(串第一个字符位置为1，操作位置以子串的起始位置记)，P代表操作后的串。

数据保证一定有解，如果有多解，任意输出一种答案即可。

BAB A
A BAA
AAB BB
6 BAB BABBBBAA

1 1 A
2 1 BAA
2 3 BABAA
2 5 BABABAA
2 4 BABBAABAA
3 5 BABBBBAA

备注:

关于样例解释

现在我们有三个替换规则：BAB->AA->BAAAAB->BB

cls要求用6步把BAB变成BABBBBAA

那么第一步我们用一下操作1，对BAB的1号位置（第一个B）进行操作，把串变成了A

第二步我们用一下操作2，对A的1号位置（A自己）进行操作，把串变成了BAA

第三步我们用一下操作2，对BAA的3号位置（最后一个A）进行操作，把串变成了BABAA

第四步我们用一下操作2，对BABAA的5号位置（最后一个A）进行操作，把串变成了BABABAA

第五步我们用一下操作2，对BABABAA的4号位置进行操作，把串变成了BABBAABAA

第六步我们用一下操作3，对BABBAABAA的5号位置进行操作，把串变成了BABBBBAA。

到此，我们用了6步完成了cls的字符串游戏