Hàm \(A.find(B)\) trả về vị trí đầu tiên xuất hiện của xâu \(B\) trong xâu \(A\). Nếu không tồn tại xâu con \(B\) trong \(A\), trả về \(-1\).

Sử dụng hàm find thực hiện các yêu cầu sau:

Cho một xâu \(S\) và \(Q\) truy vấn, mỗi truy vấn gồm có một xâu \(x\): hãy tìm vị trí đầu tiên xuất hiện của xâu \(x\) trong xâu \(S\) ban đầu. Xâu gồm các kí tự latin gồm chữ và số.

Input

• Dòng đầu ghi xâu \(S\) có độ dài không quá \(10^6\)

• Dòng thứ hai ghi \(Q\) là số lượng truy vấn

Tiếp theo là \(Q\) dòng, mỗi dòng ghi một xâu \(x\) có độ dài không quá \(10^6\)

Output

• Với mỗi truy vấn ghi kết quả trên 1 dòng là vị trí đầu tiên xuất hiện xâu \(x\) trong \(S\)

Example

Cai xac xinh xinh 
2 
xinh 
be   

8
-1