Bạn được cho một xâu có độ dài \(n\), các kí tự được đánh số từ \(1..n\). Bạn cũng được cho một vài xâu con nữa. Nhiệm vụ của bạn là với mỗi xâu con, hãy tìm vị trí đầu tiên mà nó xuất hiện trong chuỗi ban đầu, hoặc báo là vị trí đó không tồn tại.

Input

• Dòng đầu tiên của input chứa một xâu có độ dài \(n\).
• Dòng tiếp theo chứa 1 số nguyên \(k\), là số xâu con cần phải xử lý.
• \(k\) dòng tiếp theo, mỗi dòng chứa một xâu con.

Output

• In ra \(k\) số, số thứ \(i\) là vị trí đầu tiên mà xâu con thứ \(i\) xuất hiện trong xâu ban đầu (hoặc -1 nếu vị trí đó không tồn tại).

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq k \leq 5 \cdot 10^5\)
• Tổng độ dài của các xâu con không vượt quá \(5 \cdot 10^5\)

Example