Tra cứu

Tại Thư viện số quốc gia, các tài liệu được lưu trữ dưới dạng chuỗi văn bản dài liên tục, không có phân cách rõ ràng giữa các từ. Để hỗ trợ độc giả trong việc tìm kiếm nội dung một cách nhanh chóng, bạn được giao nhiệm vụ xây dựng một công cụ tra cứu đơn giản nhưng hiệu quả. Cụ thể, hệ thống sẽ nhận vào một đoạn văn bản \(S\) có độ dài \(n\) (các kí tự được đánh số từ \(1\) đến \(n\)), và một danh sách gồm \(k\) từ khoá mà người dùng cần truy vấn. Với mỗi từ khoá, hệ thống cần chỉ ra vị trí đầu tiên mà nó xuất hiện trong văn bản gốc \(S\), nếu có. Nếu từ khoá đó hoàn toàn không xuất hiện trong văn bản, hệ thống phải trả lời rằng từ khoá đó không tồn tại.

Vị trí được đánh số bắt đầu từ $1$ (tức ký tự đầu tiên của chuỗi gốc có chỉ số là $1$). Đối với mỗi truy vấn, bạn chỉ cần in ra vị trí bắt đầu đầu tiên của từ khoá trong văn bản gốc hoặc `-1` nếu không có kết quả phù hợp.

Ví dụ, nếu văn bản gốc là `quandeptrai` và các từ khoá truy vấn là `quan`, `deptrai`, và `xautrai`, thì kết quả lần lượt sẽ là $1$, $5$, và $-1$ tương ứng.

Input

• Dòng đầu chứa một chuỗi \(S\) gồm \(n\) ký tự, chỉ bao gồm các ký tự in thường tiếng Anh \((1 \le n \le 10^5)\).
• Dòng thứ hai chứa số nguyên \(k\) --- số lượng từ khóa truy vấn \((1 \le k \le 5 \cdot 10^5)\).
• \(k\) dòng tiếp theo: mỗi dòng chứa một chuỗi con \(T_i\), là một từ khóa \((1 \le |T_i| \le |S|)\). Tổng độ dài của tất cả từ khóa không vượt quá \(5 \cdot 10^5\).

Output

In ra \(k\) dòng. Dòng thứ \(i\) chứa một số nguyên:

• Là vị trí đầu tiên (tính từ 1) mà từ khóa \(T_i\) xuất hiện trong chuỗi \(S\).
• In ra -1 nếu không tồn tại.

Example

quandeptrai
3
quan
deptrai
xautrai

1
5
-1

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(|S|, k \leq 100\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(|S|, k \leq 2000\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại không có ràng buộc gì thêm.