Нормальный алгоритм Маркова задаёт способ преобразования входной строки в результирующую с помощью системы подстановок.

Каждая подстановка состоит из двух слов — образца и замены. На каждом шаге алгоритма в списке подстановок ищется первая по порядку подстановка, где образец встречается в текущей строке $$$s$$$ в качестве подстроки. Эта подстрока в $$$s$$$ меняется на слово-замену. Если образец встречается в $$$s$$$ несколько раз, то заменяется только самое левое вхождение.

В подстановке образец может быть пустым, в этом случае замена вставляется в самое начало $$$s$$$. Обычно такая подстановка пишется последней, чтобы алгоритм не зацикливался. Слово-замена также может быть пустым (при стирании образца).

Алгоритм завершается в двух случаях. Во-первых, если ни одна подстановка больше не подходит. Во-вторых, после выполнения такой подстановки, в которой слово-замена заканчивается специальным символом '.', то есть точкой (сама точка в строку $$$s$$$ не вставляется).

Приведём пример. Пусть входная строка состоит только из цифр 0 и 1. Требуется стереть все нули в конце строки. Решение:

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

Рассмотрим, как этот алгоритм работает для входной строки $$$s$$$=«10100». Вначале срабатывает последняя подстановка, вставляющая «p» в начало строки $$$s$$$. Теперь $$$s$$$=«p10100».

Далее пять раз срабатывают первая или вторая подстановки, в результате чего символ 'p' «едет» вправо до конца строки. Получится $$$s$$$=«10100p».

После этого дважды срабатывает третья подстановка, заменяющая «0p» на «p». Теперь $$$s=$$$«101p».

И, наконец, срабатывает четвёртая подстановка, которая стирает «p» и завершает алгоритм. В результате s=«101».

Задание. Придумайте нормальный алгоритм Маркова для решения следующей задачи. Входная строка $$$s$$$ содержит натуральное число. После выполнения алгоритма она должна содержать остаток от деления этого числа на 3.

В поле ответа введите ваши подстановки, разделяя слово-образец и слово-замену пробелом. Если образец пустой, то ставится один пробел и пишется слово-замена. Если слово-замена пустое, то пишется образец и при желании добавляется пробел. Одновременно и образец, и замена пустыми быть не могут.

При отправке решения в поле «Язык» выберите PHP (вам не нужно знать PHP, это просто особенность системы).

Подзадача 1 (до 20 баллов): входное число состоит из одной цифры.

Подзадача 2 (до 35 баллов): входное число состоит из двух цифр.

Подзадача 3 (до 45 баллов): входное число имеет от 3 до 9 цифр.