DNA Analysis
Biologists from the Karelian Mutation Project (KMP) have recently embarked on new research to demonstrate that humans are closely related to mammoths. To support this unusual hypothesis, scientists plan to compare the DNA of humans and mammoths.
For this comparison, DNA is divided into fragments of length n, which are then compared in sequence. Given the possibility of mutations in humans and mammoths over time, the following method for comparing fragments has been proposed.
Consider the string α. We say that α mutates into β if α can be expressed as xyz for some (possibly empty) strings x, y, and z, and β is xy^Rz, where y^R is the string y reversed (for example, "abc"^R becomes "cba"). We define strings α and β as similar if α can be transformed into β with no more than 4 mutations.
Given two DNA fragments, your task is to determine if they are similar.
Input
The input consists of two strings made up of the characters 'A', 'D', 'G', and 'T'. Both strings are of the same length, which does not exceed 30.
Output
Print "Similar" if the strings are similar, and "Different" if they are not.