Cho hai chuỗi str1 và str2.

Chúng ta nói rằng chuỗi t "chia hết" cho chuỗi s nếu và chỉ nếu chuỗi s được tạo bằng cách nối chuỗi t với chính nó một hoặc nhiều lần.
Nói cách khác, s = t + t + t + ... (nhiều lần).

Yêu cầu: Hãy tìm và trả về chuỗi có độ dài lớn nhất x sao cho x chia hết cả str1 và str2.

Input

• Dòng 1: chuỗi str1
• Dòng 2: chuỗi str2

Output

• Chuỗi con dài nhất x thỏa mãn yêu cầu (có thể là chuỗi rỗng "" nếu không tồn tại).

Ràng buộc

• 1 ≤ str1.length, str2.length ≤ 1000
• str1 và str2 chỉ gồm các chữ cái in hoa tiếng Anh (A-Z)

Ví dụ

Input:
ABCABC
ABC

Output:
ABC

Input:
ABABAB
ABAB

Output:
AB

Input:
LEET
CODE

Output:
""