Link my group on LQDOJ

Nguồn: Apex Cup 2026 in ledinhbaonam group(here: ledinhbaonam group)

Két sắt bảo mật cao của ngân hàng đã được nâng cấp hệ thống chống trộm. Trên màn hình hiển thị hai xâu ký tự \(A\) và \(B\). Mật mã mở khóa là một xâu ký tự \(W\) thỏa mãn:

1. \(W\) là một xâu con liên tiếp của xâu \(A\).
2. \(W\) là một xâu con (không nhất thiết liên tiếp) của xâu \(B\).
3. \(W\) có độ dài lớn nhất. Nếu có nhiều xâu \(W\) cùng đạt độ dài lớn nhất, hệ thống yêu cầu chọn xâu có thứ tự từ điển nhỏ nhất.

Yêu cầu: Cho hai xâu \(A\) và \(B\). Hãy tìm xâu \(W\) thỏa mãn các điều kiện trên.

Input

• Dòng thứ nhất chứa xâu \(A\) (\(1 \le \vert{}A\vert{} \le 100.000\))
• Dòng thứ hai chứa xâu \(B\) (\(1 \le \vert{}B\vert{} \le 100.000\))
• Các xâu chỉ bao gồm các chữ cái tiếng Anh viết thường từ a đến z

Output

• In ra xâu \(W\) tìm được. Nếu không tồn tại xâu nào, in ra -1

Example

cabcd
axbxc

abc