Sổ Đếm Mẫu

Cho một văn bản và một danh sách mẫu. Một mẫu xuất hiện khi nó bằng một đoạn ký tự liên tiếp của văn bản. Các lần xuất hiện có thể chồng lấn.

Với mỗi mẫu, đếm số vị trí bắt đầu mà mẫu xuất hiện như một xâu con liên tiếp của văn bản; các lần xuất hiện được phép chồng lấn.

Input

• Dòng đầu chứa văn bản $S$.
• 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.

Output

• In $k$ dòng; dòng thứ $i$ là số lần xuất hiện của mẫu thứ $i$.

Constraints

• $1\le |S|\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$.
• Văn bản và mọi mẫu chỉ gồm các chữ cái thường $a$ đến $z$.

Scoring

• Subtask $1$ ($50$ điểm): $10$ test nhỏ, phù hợp với cách đối chiếu trực tiếp từng mẫu.
• Subtask $2$ ($50$ điểm): $10$ test không có giới hạn bổ sung.

Example

aaaa
3
a
aa
aaa

4
3
2