Tý có xâu \(S\) và \(Q\) truy vấn. Mỗi truy vấn cho xâu \(P\), tìm vị trí xuất hiện đầu tiên (0-indexed) của \(P\) trong \(S\).

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

• Dòng 1: xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Dòng 2: số nguyên \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp: mỗi dòng là xâu \(P\).

Định dạng đầu ra

• Với mỗi truy vấn, in ra vị trí xuất hiện đầu tiên của \(P\) trong \(S\). Nếu không xuất hiện, in ra -1.

Ví dụ

Input:

abacaba
3
aba
bac
xyz

Output:

0
2
-1

Ràng buộc

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