Đột biến

Các nhà sinh vật học ở Viện nghiên cứu Di truyền XYZ đang thực hiện dự án nghiên cứu về sự gần gũi giữa các loài trong quá trình tiến hóa. Phương pháp nghiên cứu của họ là chia chuỗi DNA thành các đoạn có độ dài $n$ và so sánh các đoạn với nhau. Một loài phát triển thành loài khác thông qua đột biến di truyền.

Xét một đoạn DNA $\alpha$ tách được. Người ta coi $\alpha$ đột biến thành $\beta$ nếu $\alpha =xyz$ với các xâu $x,y,z$ nào đó (có thể rỗng), còn $\beta =x{y}^{R}z$, trong đó $y^R$ là $y$ viết theo trình tự ngược lại. Nói cách khác, một lần đột biến là đảo ngược một đoạn ký tự liên tiếp. Nói $\alpha$ gần giống $\beta$ nếu $\alpha$ có thể biến thành $\beta$ sau không quá $4$ lần đột biến (kể cả $0$ lần, tức là hai đoạn giống hệt nhau thì gần giống nhau).

Ví dụ, ATGAATGA gần giống AGGAATTA vì: ATGAATGA $\to$ AGTAAGTA $\to$ AGGAATTA.

Yêu cầu: Cho hai đoạn DNA cùng độ dài $n$, các ký tự trong DNA là A, D, G, T. Hãy xác định chúng có gần giống nhau hay không và đưa ra thông báo Similar (gần giống nhau) hoặc Different (khác nhau).

Dữ liệu vào

• Dòng đầu tiên chứa đoạn DNA thứ nhất.
• Dòng thứ hai chứa đoạn DNA thứ hai.

Dữ liệu ra

In ra Similar nếu hai đoạn DNA gần giống nhau, hoặc Different nếu khác nhau.

Ràng buộc

• Hai đoạn DNA có cùng độ dài $n$, $1\le n\le 30$.
• Mỗi ký tự là một trong bốn chữ cái in hoa A, D, G, T.

Ví dụ