Cho văn bản \(T\) và xâu mẫu \(P\). Tìm vị trí xuất hiện cuối cùng của \(P\) trong \(T\) (không overlap). Nếu không có, in ra -1.

Định dạng đầu vào

• Dòng 1: văn bản \(T\).
• Dòng 2: xâu mẫu \(P\).

Định dạng đầu ra

• Một số nguyên là vị trí cuối cùng, hoặc -1.

Ví dụ

Input:

aabcabaab
ab

Output:

7

Ràng buộc

• 100% số điểm: \(|T|, |P| \le 10^5\).