Республиканская олимпиада по информатике 2012 года за 9 класс | Казахстанские олимпиады

Одна из задач генетического анализа заключается в определении степени похожести двух последовательностей нуклеотидов. Последовательность нуклеотидов — это строка из букв $A,$ $G,$ $C,$ $T.$ Последовательности можно циклически сдвигать друг относительно друга. Степенью похожести двух последовательностей назовем максимально возможное количество совпадений символов в соответствующих позициях строк. Для заданных двух последовательностей определите степень их похожести.

Формат входного файла

Входной файл содержит две строки одинаковой длины, состоящие из символов $A,$ $G,$ $C,$ $T.$ Строки не пустые и их длина не превышает 50000.

Формат выходного файла

На первой строке выходного файла выведите целое число — степень похожести заданных строк. На следующих двух строках выведите исходные строки, циклически сдвинутые так, что достигается полученная степень похожести. Строки выводите в таком же порядке, как они даны во входном файле.

Примеры

Вход

ACAGTG
AGTGTC

Выход

5
ACAGTG
TCAGTG