A substitution rule describes how to take a sequence of symbols and convert it into a different sequence of symbols. For example, , is a substitution rule which means that can be replaced with . Using this rule, the sequence would be transformed into the sequence (the substituted symbols are in **bold**).

In this task, you will be given three substitution rules, a starting sequence of symbols and a final sequence of symbols. You are to use the substitution rules to convert the starting sequence into the final sequence, using a specified number of substitutions.

For example, if the three substitution rules were:

we could convert the sequence into in steps, by the following substitutions:

where the symbols to be replaced are shown in **bold**. More specifically, from the initial sequence , substitute rule starting at position , to get the result . From , substitute rule , starting at position , to get the result . From , substitute rule , starting at position , to get the result . From , substitute rule , starting at position , to get the result , which is the final sequence.

#### Input Specification

The first three lines will contain the substitution rules. Each substitution rule will be a sequence of `A`

's and `B`

's, followed by a space following by another sequence of `A`

's and `B`

's. Both sequences will have between one and five symbols.

The next line contains three space separated values, , and . The value is an integer specifying the number of steps that must be used, and the values (the initial sequence) and (the final sequence) are sequences of `A`

's and `B`

's, where there are at least one and at most symbols in and at least one and at most symbols in .

For of the marks available, .

For an additional of the available marks, .

**Due to the official test data being weak, an additional subtask worth 15 marks has been
added that consists of tests constructed to break solutions that are incorrect but AC on the official
test data. Data are provided by ** .

#### Output Specification

The output will be lines long and describes the substitutions in order.

Line of the output will contain three space-separated values, , , and :

- is the substitution rule number (either , or ) that will be used.
- is the starting position index of where the substitution rule will be applied in the sequence. Notice that the string is -indexed (i.e., the first character of the string is at index ).
- is the sequence that results from this substitution. Specifically, is the sequence of symbols that results by applying substitution rule starting at position from the previous sequence of symbols, , where we define to be the initial sequence . Note that , the final sequence.

There will always be at least one sequence of substitutions that will convert into . If there is more than one possible sequence of substitutions, any valid sequence will be accepted.

#### Sample Input

```
AA AB
AB BB
B AA
4 AB AAAB
```

#### Possible Output for Sample Input

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

#### Explanation of Output for Sample Input

This is the example outlined in the problem description. Note that the following is another possible valid substitution sequence:

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

Specifically, showing the substitutions in **bold**, we get

## Comments

Could somebody share their solution for this problem in c++. I have a hard time imagining how I would approach this.Thx.

If you brute force isn't it still O(3^S)~1e7?

hello kevin！ it is more than that I think example: bbbbbbbbbbb. more that one way to do b->aa

Why is the time limit so low? Isn't it supposed to be at least 2.0s?

This problem is so hard

This question really should be worth much more points.

I should stop working on this one (it's putting me behind in other tasks, oops!), but I can't get in under the 1 second time limit. My solutions all use recursion-based DFS. I started with Python3, converted to C, added memoization (hashing based on number of steps and the current string), added bidirectional/meet-in-the-middle search... each of these steps has helped, but not sufficiently. Now I'm stuck. Can anyone help? I've learned a lot with this problem, and I'm grateful for that, but it would be nice to see how to solve this more quickly so that I can fully move on.

Could you please clarify what you mean by "hashing based on number of steps and the current string"? I'm also trying to speed up my solution with memoization, but I can't get it to work

I'm trying this problem for around 6 months now, and did all the things you've done but still can't pass the last test case. One other thing I did is calculating the number of times you can apply a rule by creating systems of equations and solving them. You might try that out as well, but I don't think it'll be very useful.

Just 8 score...

use memoization, you shud be able to get 15/30

How does one not TLE?

Ideas anyone? I'm using recursion and getting TLE. Thanks!

Elegant how they changed the point value to 15 from 35.

Can someone tell me when people can get an AC with an incorrect answer? (i.e. you get AC but you don't get full marks)

For example, when your code is correct for some answers.

But wouldn't that be a WA? And why am I getting downvotes...

There could be a mistake in your code. However, the original test data would never be able to exploit your mistake, and that's how you could get away with an incorrect answer.