Анализ ДНК
Биологи Карельского Мутационного Проекта (КМП) недавно решили начать новые исследования, которые должны доказать, что люди — близкие родственники мамонтов. Чтобы доказать это странное предположение, ученые планируют сравнить ДНК людей и мамонтов.
Для сравнения ДНК разделяется на фрагменты длины n и они последовательно сравниваются. Поскольку в процессе развития у людей и мамонтов могли происходить мутации, предлагается следующий способ сравнения фрагментов.
Рассмотрим строку α. Будем говорить, что α мутирует в β, если α = xyz для некоторых (возможно пустых) x, y и z, а β = xy^Rz, где y^R означает строку y, записанную задом наперед (например, "abc"^R = "cba"). Будем говорить, что строки α и β похожи, если α может быть превращена в β не более чем за 4 мутации.
По двум данным фрагментам ДНК определите, похожи ли они.
Входные данные
Входной файл содержит две строки, состоящие из символов 'A', 'D', 'G' и 'T'. Строки имеют одинаковую длину, не превышающую 30.
Выходные данные
Выведите в выходной файл "Similar", если строки похожи, и "Different", если нет.