Xâu con chung nhỏ nhất từ điển

Xâu \(R\) là xâu con của xâu \(S\) nếu \(R\) nhận được từ \(S\) bằng cách xoá đi một số ký tự và giữ nguyên thứ tự các ký tự còn lại.

Cho hai xâu \(A\) và \(B\). Hãy in ra một xâu con chung của \(A\) và \(B\) có độ dài lớn nhất. Vì có thể có nhiều xâu như vậy, hãy in ra xâu nhỏ nhất theo thứ tự từ điển (so sánh theo mã ASCII từng ký tự) trong số các xâu con chung có độ dài lớn nhất. Nếu không có ký tự nào chung, in ra một dòng trống.

Input

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

Output

In ra một dòng là xâu con chung dài nhất, nhỏ nhất theo thứ tự từ điển.

Constraints

• Mỗi xâu có độ dài từ \(1\) đến \(2000\).
• Các xâu chỉ gồm các ký tự in được có mã ASCII từ \(33\) đến \(126\) (không chứa dấu cách).

Sample Input 1

banana
ananas

Sample Output 1

anana

Sample Input 2

k7#m2q!9
7k2#q9m!

Sample Output 2

7#m!

Explanation

Ở ví dụ 1 xâu con chung dài nhất có độ dài \(5\) và anana là xâu duy nhất. Ở ví dụ 2, độ dài lớn nhất là \(4\); trong các xâu con chung độ dài \(4\), xâu 7#m! có thứ tự từ điển nhỏ nhất.