Trong bài này, ta gọi xâu x là xâu con của xâu y nếu như có thể xóa một số kí tự của y (có thể không xóa kí tự nào) để nó trở thành xâu x. VD xâu "ABC" là xâu con của "AABDEC" nhưng không phải là xâu con của "BACCA".

Cho 2 xâu a và b. Tìm xâu con chung dài nhất của a và b. Nếu có nhiều xâu con chung có cùng độ dài thì chọn xâu lớn nhất.

Input

Dòng 1: Xâu a;

Dòng 2: Xâu b;

Mỗi xâu không quá 1000 kí tự;

Output

Ghi ra xâu con chung lớn nhất.

Ví dụ:

Input

abcdgh
bacesgod

Output

bcg

Giải thích: Các xâu con chung dài nhất của 2 xâu đã cho trong ví dụ là 'acg', 'bcg', 'acd', 'bcd' (đều có độ dài 3). Trong đó xâu lớn nhất là 'bcg'.

Nguồn

Ví dụ:

Input

3 3
0 2 3
4 5 6
7 8 0

Output

32

Ví dụ:

Input

3 4 2 6
1 1 1 7
2 8 9 1
1 3 2 3
1
2

Output

5
3

Nguồn