Перетворення ДНК#4176

Перетворення ДНК

1 секунда

64 мегабайти

Легка

Біологи лабораторії Advanced Cellular Mechanics Lab. (ACM Lab.) займаються дослідженнями в галузі геномів і ДНК. Нещодавно в цій лабораторії була розроблена технологія, що дозволяє досить дешево здійснювати певні перетворення з ланцюгом ДНК.

Уявімо ланцюг ДНК як рядок довжини $n$ , що складається з символів множини ${A, G, C, T}$ \{A, G, C, T\}. Елементарне перетворення, яке можуть виконувати біологи лабораторії, полягає в розвороті підрядка з $l$ -го по $r$ -й символ (де цілі числа $l$ і $r$ вибираються так, що $1 \leq l \leq r \leq n$ 1 \leq l \leq r \leq n). Таким чином, з рядка $a_{1} a_{2} \dots a_{l} a_{l + 1} \dots a_{r - 1} a_{r} \dots a_{n}$ a_1 a_2 \ldots a_l a_{l+1} \ldots a_{r-1} a_r \ldots a_n утворюється рядок $a_{1} a_{2} \dots a_{r} a_{r - 1} \dots a_{l + 1} a_{l} \dots a_{n}$ a_1 a_2 \ldots a_r a_{r-1} \ldots a_{l+1} a_l \ldots a_n.

Зараз біологи розробляють програмно-апаратний комплекс для виконання перетворень ДНК. Однією з його функцій буде перетворення вихідного ланцюга ДНК у потрібний.

Ваше завдання — написати програму, яка за вихідним і потрібним ланцюгами ДНК знайде необхідну для цього послідовність елементарних перетворень.

Вхідні дані

Перший рядок вхідного файлу містить опис вихідного ланцюга ДНК, другий рядок — опис потрібного ланцюга ДНК. Довжини обох ланцюгів збігаються і не перевищують $5000$ . Кожен з ланцюгів містить лише символи з множини ${A, G, C, T}$ \{A, G, C, T\}.

Гарантується, що шукана послідовність перетворень існує.

Вихідні дані

У першому рядку вихідного файлу виведіть кількість $k$ перетворень у побудованому рішенні. Число $k$ має бути невід'ємним і не повинно перевищувати $4999$ .

Далі виведіть $k$ рядків, що описують побудовану послідовність елементарних перетворень. Кожен з рядків повинен містити два числа: $l_{i}$ l_i і $r_{i}$ r_i — відповідно лівий і правий кінець відрізка, що розгортається на $i$ -му кроці.

Приклади

Приклад 1