Преобразование ДНК
Биологи лаборатории Advanced Celluar Mechanics Lab. (ACM Lab.) занимаются исследованиями в области геномов и ДНК. Недавно в этой лаборатории была разработана технология, позволяющая достаточно дёшево производить с цепочкой ДНК некоторые преобразования.
Представим себе цепочку ДНК как строку длины n из символов из множества {A, G, C, T}. Элементарное преобразование, которое умеют производить биологи лаборатории, представляет собой разворот подстроки с l-го по r-й символ (целые числа l и r выбираются так, что 1 ≤ l ≤ r ≤ n). Таким образом, из строки a_1a_2...a_la_{l+1}...a_{r−1}a_r...a_n получается строка a_1a_2...a_ra_{r−1}...a_{l+1}a_l...a_n.
Теперь биологи разрабатывают программно-аппаратный комплекс для выполнения преобразований ДНК. Одной из его функций будет преобразование исходной цепочки ДНК в требуемую.
Ваша задача - написать программу, которая по исъодной и требуемой цепочкам ДНК будет находить необходимую для этого цепочку элементарных преобразований.
Входные данные
Первая строка входного файла содержит описание исходной цепочки ДНК, вторая строка - описание требуемой цепочки ДНК. Длины обеих цепочек совпадают и не превышают 5000. Каждая из цепочек содержит только символы из множества {A, G, C, T}.
Гарантируется, что искомая последовательность преобразований существует.
Выходные данные
В первой строке выходного файла выведите количество k преобразований в построенном решении. Числоk должно быть неотрицательным и не должно превышать 4999.
Далее выведите k строк, описывающих построенную последовательность элементарных преобразований. Каждая из строк должна содержать два числа: l_i и r_i - соответственно левый и правый конец разворачиваемого на i-м шаге отрезка.