Bạn được cho một chuỗi và một tập hợp các mẫu (patterns). Nhiệm vụ của bạn là, với mỗi mẫu, hãy tìm vị trí xuất hiện đầu tiên của nó trong chuỗi (tính theo chỉ số bắt đầu từ 1). Nếu mẫu không xuất hiện trong chuỗi, in ra -1.

Input:

Dòng đầu tiên chứa một chuỗi có độ dài n.

Dòng thứ hai chứa một số nguyên k — số lượng mẫu.

Sau đó là k dòng, mỗi dòng chứa một mẫu.

Chuỗi và các mẫu chỉ bao gồm các ký tự thường a–z.

Output:

In ra k dòng.

Dòng thứ i chứa vị trí xuất hiện đầu tiên (1-indexed) của mẫu thứ i trong chuỗi.

Nếu mẫu không xuất hiện, in ra -1.

Ràng buộc:

~1 \le n \le 10^5~

~1 \le k \le 5 \cdot 10^5~

Tổng độ dài của tất cả các mẫu ≤ ~5 ⋅ 10^5~

Ví dụ :

Input:

aybabtu
3
bab
abc
a

Output:

3
-1
1