A substitution rule describes how to take a
sequence of symbols and convert it into a different sequence of symbols.
For example, ABA \(\rightarrow\) BBB,
is a substitution rule which means that ABA can be replaced with BBB.
Using this rule, the sequence AABAA would
be transformed into the sequence ABBBA (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:

• AA \(\rightarrow\) AB

• AB \(\rightarrow\) BB

• B \(\rightarrow\) AA

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

AB \(\rightarrow\)
BB \(\rightarrow\)
AAB \(\rightarrow\)
AAAA \(\rightarrow\) AAAB,

where the symbols to be replaced are shown in
bold. More specifically, from the initial
sequence AB, substitute rule 2 starting at position 1, to get the result
BB. From BB, substitute rule 3, starting at position 1, to get the
result AAB. From AAB, substitute rule 3, starting at position 3, to get
the result AAAA. From AAAA, substitute rule 1, starting at position 3,
to get the result AAAB, which is the final sequence.

Possible Output for Sample Input

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

\(1 \leq S \leq 15\)
\(S \le 6\)
\(S \le 12\)

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, \(S\), \(I\)
and \(F\). The value \(S\) (\(1 \leq S \leq 15\)) is an integer specifying the number of steps that must
be used, and the values \(I\) (the
initial sequence) and \(F\) (the final
sequence) are sequences of A’s and
B’s, where there are at least one and at most
5 symbols in \(I\) and at least one and
at most 50 symbols in \(F\).

For 7 of the 15 marks available, \(S \le 6\).

For an additional 7 of the 15 available marks, \(S \le 12\).

The output will be \(S\) lines long and
describes the substitutions in order.

Line \(i\) of the output will
contain three space-separated values, \(R_i\), \(P_i\), and \(W_i\):

• \(R_i\) is the substitution rule
  number (either 1, 2
  or 3) that will be used.

• \(P_i\) is the starting position
  index of where the substitution rule will be applied in the sequence.
  Notice that the string is 1-indexed (i.e., the first character of the
  string is at index 1).

• \(W_i\) is the sequence that
  results from this substitution. Specifically, \(W_i\) is the sequence of symbols that
  results by applying substitution rule \(R_i\) starting at position \(P_i\) from the previous sequence of
  symbols, \(W_{i-1}\), where we define
  \(W_0\) to be the initial sequence
  \(I\). Note that \(W_S = F\), the final sequence.

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

생성자가 기록되지 않았습니다.

출처 CCC 2019 Junior