Ta gọi xâu \(R\) là xâu con của xâu \(S\) nếu ta có thể thu được xâu \(R\) bằng cách xóa đi một vài ký tự của xâu \(S\) và giữ nguyên thứ tự các ký tự còn lại.

Xâu ký tự \(C\) được gọi là xâu con chung của hai xâu \(A\) và \(B\) nếu \(C\) là xâu con của \(A\) và \(C\) là xâu con của \(B\). Trong bài tập này nhiệm vụ của bạn cần tìm xâu con chung dài nhất của hai xâu \(A\) và \(B\)

Dữ liệu vào

• Dòng thứ nhất chứa xâu \(A\).
• Dòng thứ hai chứa xâu \(B\).
• \(|A|,|B| \le 2000\)

Dữ liệu ra

• In ra một xâu con chung dài nhất bất kỳ tìm được.

Input 1

abcd
aabd

Output 1

abd

Input 2

abc1def2ghi3
abcdefghi123

Output 2

abcdefghi3