Vị Trí Đầu Tiên

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, tìm vị trí bắt đầu nhỏ nhất theo chỉ số $1$ mà mẫu xuất hiện trong văn bản; nếu không có thì trả về $-1$.

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à vị trí bắt đầu nhỏ nhất của mẫu thứ $i$, hoặc $-1$ nếu mẫu không xuất hiện.

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

cababa
4
aba
cab
bb
a

2
1
-1
2