Cho hai xâu \(s\) và \(t\) chỉ gồm các chữ cái thường \('a'..'z'\). Tìm xâu con chung dài nhất (subsequence) của hai xâu \(s\) và \(t\)

Input

• Dòng thứ nhất chứa xâu \(s(1\le |s|\le 3000)\)

• Dòng thứ hai chứa xâu \(t(1\le |t|\le 3000)\)

Output

• In ra xâu chung dài nhất cần tìm. Nếu có nhiều đáp án in ra bất kì !

Chú ý: Một xâu con của một xâu \(x\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(x\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Example

axyb
abyxb

axb