Cho một chuỗi ký tự $S$ và một danh sách các mẫu (pattern) $P₁$, $P₂$, ..., $Pₘ$. Với mỗi mẫu $Pᵢ$, hãy đếm số lần nó xuất hiện trong chuỗi $S$ dưới dạng chuỗi con liên tiếp (substring).

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 cần kiểm tra.
• Sau đó là $k$ dòng, mỗi dòng chứa một mẫu (pattern) gồm các ký tự từ 'a' đến 'z'.

Output:
Với mỗi mẫu, in ra số vị trí mà mẫu đó xuất hiện trong chuỗi ban đầu.

Constraints:

• $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 không vượt quá $5 \cdot 10^5$

Example
Sample Input:

aybabtu
3
bab
abc
a

Sample Output:

1
0
2