Huyen là nhà khoa học đứng đầu viện nghiên cứu hoàng gia của đế quốc Byteland, chuyên môn của cô là lĩnh vực sinh vật học. Hiện tại Huyen đang có chuyến công tác tại đất nước Switzerland để nghiên cứu giải mã bộ gene của một cá thể động vật quý hiếm X đã bị đột biến ở Byteland. Trình tự DNA là chuỗi các ký tự liên tiếp nhau nhằm biểu diễn cấu trúc chính của một dải hay phân tử DNA thực hoặc tổng hợp, mà có khả năng mang thông tin về gene di truyền.

Khi tiến hành nghiên cứu về mã gene của cá thể động vật X, nhóm nghiên cứu nhận thấy có một đoạn gene bị đột biến làm hoán vị trình tự DNA. Việc cần làm lúc này là đem so đoạn DNA bị đột biến đó với một chuỗi DNA gốc của một cá thể khỏe mạnh để tìm ra vị trí bị đột biến nhằm tính toán mức độ và nguyên nhân xảy ra đột biến.

Hay nói cách khác, cho một chuỗi ký tự S (gồm các chữ cái in hoa từ \(A\) đến \(Z\)) thể hiện dải DNA của một cá thể khỏe mạnh và một chuỗi ký tự X thể hiện đoạn DNA bị đột biến. Cần tìm một hoán vị của X sao cho nó là xâu con liên tiếp của S. Kết quả sẽ là vị trí xuất hiện đầu tiên (từ trái sang) của hoán vị của X nằm trong S, dữ liệu luôn đảm bảo sự xuất hiện của ít nhất một hoán vị của chuỗi X trong S.

Vì hệ thống máy tính của phòng thí nghiệm hiện đang bị sự cố nên Huyen không thể lập trình để phân tích mã gene. Vì vậy cô ấy quyết định gửi thông tin về đoạn gene cho các bạn học sinh ITK20 nhờ sự giúp đỡ, các bạn hãy giúp cô ấy nhé!

Input

• Dòng đầu tiên chứa chuỗi ký tự S không rỗng.
• Dòng thứ hai gồm một số nguyên dương Q thể hiện số truy vấn.
• Tiếp theo là Q dòng, mỗi dòng gồm một chuỗi ký tự X không rỗng.

Output

• In ra Q dòng, mỗi dòng gồm một số duy nhất là chỉ số của vị trí đầu tiên xuất hiện hoán vị của X trong S (chuỗi S được đánh chỉ số từ \(1\)).

Ví dụ

Sample input

AFDEGGHK
2
EGD
GKHG

Sample output

3
5

Giải thích ví dụ

Chuỗi X có một hoán vị là DEG và nó xuất hiện ở vị trí \(3\) trong chuỗi S.

Ràng buộc

• Subtask 1 (20%): \(Q\leq10^3, |S|\leq100, |X|\leq5\).
• Subtask 2 (40%): \(Q\leq10^4, |S|\leq10^5, |X|\leq6\).
• Subtask 3 (40%): \(Q\leq10^3, |S|\leq10^5, |X|\leq10^3\).