3. Normal Algorithm
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A Markov normal algorithm defines a method for transforming an input string into a result string using a system of substitutions.

Each substitution consists of two words: a pattern and a replacement. At each step of the algorithm, the list of substitutions is scanned to find the first one where the pattern appears as a substring within the current string $$$s$$$. This substring in $$$s$$$ is then replaced by the replacement word. If the pattern appears multiple times in $$$s$$$, only the leftmost occurrence is replaced.

A pattern in a substitution may be empty; in this case, the replacement word is inserted at the very beginning of $$$s$$$. Typically, such a substitution is placed last to prevent the algorithm from entering an infinite loop. The replacement word may also be empty (effectively deleting the pattern).

The algorithm terminates in two cases: first, if no further substitutions are applicable; second, if a substitution is performed where the replacement word ends with a special symbol — a period ('.'), which is not itself inserted into the string $$$s$$$.

Consider an example. Suppose the input string consists only of the digits 0 and 1, and the task is to delete all zeros at the end of the string. The solution is: 

p1 1p
p0 0p
0p p
p . 
p

Let's examine how this algorithm processes the input string $$$s = \text{"10100"}$$$. First, the final substitution is applied, inserting "p" at the beginning of $$$s$$$. Now, $$$s = \text{"p10100"}$$$.

Next, the first or second substitution is applied five times, causing the symbol 'p' to "move" to the right until it reaches the end of the string. The result is $$$s = \text{"10100p"}$$$. After this, the third substitution is applied twice, replacing "0p" with "p". Now, $$$s = \text{"101p"}$$$.

Finally, the fourth substitution is applied, which deletes "p" and terminates the algorithm. As a result, $$$s = \text{"101"}$$$.

Your task. Design a Markov normal algorithm to solve the following problem. The input string $$$s$$$ contains a natural number. After the algorithm has run, the string should contain the remainder when this number is divided by 3.

In the answer field, enter your substitutions, separating the pattern (the string to be replaced) and the replacement string with a space. If the pattern is empty, insert a single space followed by the replacement string. If the replacement string is empty, simply provide the pattern (you may optionally add a space). Both the pattern and the replacement string cannot be empty at the same time.

When submitting your solution, select "PHP" in the "Language" field (you do not need to know PHP; this is simply a feature of the system).

Scoring

Subtask 1 (up to 20 points): the input number consists of a single digit.

Subtask 2 (up to 35 points): the input number consists of two digits.

Subtask 3 (up to 45 points): the input number has between 3 and 9 digits.

Note

To write and debug your program, you can use the Markov normal algorithm simulator, which can be downloaded here: https://kpolyakov.spb.ru/prog/nma.htm (the interface is in Russian only).

To copy your solution from the simulator, go to the "File" menu, select "Export program" (do not confuse this with "Save"), and export the program to a text file. Copy the entire contents of this file into the response field, or submit the file itself.

Technical constraints: no more than 100 substitutions, each substitution no longer than 20 characters, and a maximum of 1000 algorithm steps. Substitutions may only contain digits, uppercase and lowercase Latin letters, and the period character ('.').