Dãy con chung may mắn

Một dãy con của một xâu là dãy thu được bằng cách xóa đi một số ký tự (có thể không xóa ký tự nào) mà không thay đổi thứ tự các ký tự còn lại. Ví dụ, BDF là một dãy con của ABCDEF. Một xâu con của một xâu là một đoạn liên tiếp các ký tự của xâu đó. Ví dụ, BCD là một xâu con của ABCDEF.

Cho hai xâu $s_1$, $s_2$ và một xâu thứ ba tên là $virus$. Hãy tìm dãy con chung dài nhất của $s_1$ và $s_2$ sao cho nó không chứa $virus$ như một xâu con (đoạn liên tiếp).

Nếu có nhiều đáp án thỏa mãn, in ra bất kỳ đáp án nào.

Dữ liệu vào

Gồm ba dòng, lần lượt là các xâu $s_1$, $s_2$ và $virus$. Mỗi xâu chỉ gồm các chữ cái in hoa trong bảng chữ cái tiếng Anh.

Dữ liệu ra

In ra dãy con chung dài nhất của $s_1$ và $s_2$ mà không chứa $virus$ như một xâu con. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Nếu không tồn tại dãy con chung hợp lệ nào có độ dài dương, in ra số $0$.

Ràng buộc

• $1\le |s_1|,|s_2|,|virus|\le 100$

Ví dụ