Рядковий автомат <<Гомер-2015>> приймає на вхід рядок символів і повертає деякий рядок як результат. В автомата є певний набір інструкцій --- список правил заміни. Кожнеправило складається з підрядка, який потрібно замінити, і рядка, на який цей підрядок потрібно замінити. Автомат послідовно робить такі операції: шукає першу в списку заміну таку, що поточний рядок містить відповідний підрядок, міняє перше входження цього підрядка на відповідний рядок-заміну і повторює все спочатку. Коли жоден підрядок у поточному рядку не міститься, автомат повертає цей рядок як результат. Список замін автомата називається \textit{програмою}. Кількість правил замін називається \textit{розміром програми}. Кількість зроблених замін на конкретних вхідних даних називається \textit{кількістю операцій}. Розглянемо приклад, коли на вхід автомат приймає рядок \textit{\textbf{abcbca}}, а його програма розміру 2 має такий вигляд: 1) \textit{\textbf{bac → c}} і 2)\textit{\textbf{ bc → cba}}. Порядок дій автомата такий: Поточним рядком є \textbf{abcbca}. \begin{enumerate} \item Оскільки \textit{\textbf{abcbca}} не містить підрядк \textit{\textbf{аbac}} з першого правила, автомат переходить до другого правила. \item Оскільки \textit{\textbf{abcbca}} містить підрядок \textit{\textbf{bc}} з другого правила, автомат заміняє перше входження цього підрядка на \textit{\textbf{cba}} і повертається на початок. \item Поточним рядком є \textit{\textbf{acbabca}}. \item Оскільки \textit{\textbf{acbabca}} не містить підрядк \textit{\textbf{аbac}} з першого правила, автомат переходить до другого правила. \item Оскільки \textit{\textbf{acbabca}} містить підрядок \textit{\textbf{bc}} з другого правила, автомат заміняє перше (і єдине) входження цього підрядка на \textit{\textbf{cba}} і повертається на початок. \item Поточним рядком є \textit{\textbf{acbacbaa}}. \item Оскільки \textit{\textbf{acbacbaa}} містить підрядок \textit{\textbf{bac}} з першого правила, автомат заміняє перше (і єдине) входження цього підрядка на \textit{\textbf{c}} і повертається на початок. \item Поточним рядком є \textit{\textbf{accbaa}}. \item Оскільки \textit{\textbf{accbaa}} не містить підрядк \textit{\textbf{аbac}} з першого правила, автомат переходить до другого правила. \item Оскільки \textit{\textbf{accbaa}} не містить підрядк \textit{\textbf{аbc}} з другого правила, автомат намагається перейти до наступного правила. \item Оскільки правила закінчилися, автомат повертає рядок \textit{\textbf{accbaa}} як результат. \end{enumerate} Таким чином, з рядка \textit{\textbf{abcbca}} автомат утворив \textit{\textbf{accbaa}}. Кількість операцій у даному випадку дорівнює 3: замінили \textit{\textbf{bc}} на \textit{\textbf{cba}}, потім ще раз \textit{\textbf{bc}} на \textit{\textbf{cba}}, далі \textit{\textbf{bac}} на \textit{\textbf{c}}. \textit{\textbf{Завдання}} Напишіть набір програм для рядкового автомата, що вирішують різноманітні задачі перетворення рядків (див. нижче). Для кожної підзадачі ви здаєте лише текст програми рядкового автомата.За кожну підзадачу ви отримуєте або повний бал за відповідну підзадачу, якщо програма пройшла всі її тести, або нуль, якщо хоча б один тест даної підзадачі не пройдено. \textbf{Обмеження} У кожному правилі довжина як підрядка пошуку, так і рядка заміни не повинна перевищувати \textbf{10 }символів (але в сумі вони можуть бути довшими); при цьому рядок заміни може бути порожнім, а підрядок пошуку --- ні. Автомат завжди може оперувати такими символами: цифри, малі та великі латинські літери (причому малі та великі літери в розумінні автомата --- різні символи), а також символ <<плюс>> (+). Ви можете користуватися всіма цими символами як у підрядках пошуку, так і в рядках заміни в усіх підзадачах. Розмір однієї програми не може перевищувати \textbf{100.} Для жодних вхіднихданих кількість операцій не повинна перевищувати 1000. Означення розміру програми та кількості операцій див. вище. \textbf{Перевірка за допомогою емулятора} В електронному варіанті умов наведено посилання для завантаження програми, що емулює рядковий автомат та надає допоміжну інформацію про перебіг виконання програми. Щоб використати емулятор, розташуйте його в окремому каталозі, створіть у цьому каталозі файл program.txt з текстом програми, а також файл input.txt, у який введіть вхідний рядок для вашої програми (можна додати або не додавати перенесення рядка в кінці файла), та запустіть програму-емулятор. Вона створить такі файли: !output.txt: вихідний рядок автомата (якщо програма чи вхідні дані некоректні або кількість операцій перевищує обмеження, файл не буде створено / буде видалено). !debug.txt:у кожному рядку цього файла вказано стан рядка після відповідної кількості операцій (якщо програма чи вхідні дані некоректні, цей файл не буде створено / буде видалено; якщо кількість операцій перевищує обмеження, файл міститиме стан рядка тільки до моменту, коли було перевищено обмеження). !info.txt: у першому рядку цього файла вказано, чи є коректними програма та вхідні дані (а якщо вони некоректні, то чому); якщо програма та вхідні дані коректні, у другому рядку вказано кількість операцій виконаної програми; у третьому рядку вказано розмір програми; у четвертому рядку вказано довжину найдовшого рядка пошуку та довжину найдовшого рядка заміни. Додатково емулятору можна передавати до чотирьох параметрів командного рядка: обмеження на кількість операцій, на розмір програми, на довжину рядка пошуку та на довжину рядка заміни. Наприклад, якщо запустити емулятор командою auto.exe 2000 100 15, обмеженням на кількість операцій буде встановлено 2000 (замість 1000); обмеження на розмір програми буде стандартним (100); обмеження на довжину рядка пошуку --- 15; невказане в параметрах командного рядка обмеження на довжину рядка заміни також залишиться стандартним (10). \textbf{Підзадача 1 (5 балів)} На вході --- рядок з цифр довжини від \textit{\textbf{1}} до \textit{\textbf{20}} включно. На виході --- рядок із тих самих цифр у порядку від найменших до найбільших. Приклад: \textit{\textbf{9101→0119}}.