Đếm Vị Trí Của Mẫu

Cho văn bản $T$ và nhiều mẫu. Với mỗi mẫu $P$, hãy đếm số vị trí bắt đầu sao cho đoạn liên tiếp của $T$ từ vị trí đó bằng $P$. Hai lần xuất hiện chồng lấn vẫn được tính là hai vị trí khác nhau.

Input

• Dòng đầu chứa văn bản $T$.
• Dòng thứ hai chứa số nguyên $k$.
• $k$ dòng tiếp theo, mỗi dòng chứa một mẫu $P_i$.

Output

• Với mỗi mẫu theo thứ tự nhập, in số lần xuất hiện của mẫu trên một dòng riêng.

Constraints

• $1\le |T|\le 10^5$.
• $1\le k\le 5\cdot 10^5$.
• Tổng độ dài của $k$ mẫu không vượt quá $5\cdot 10^5$.
• $T$ và mọi mẫu chỉ gồm các chữ cái thường tiếng Anh từ $a$ đến $z$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $|T|\le 3000,k\le 3000$ và tổng độ dài các mẫu không vượt quá $3000$.

• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

aaaaa
4
a
aa
aaa
b

5
4
3
0