Cho một xâu và các mẫu, hãy đếm với mỗi mẫu số vị trí mà nó xuất hiện trong xâu.

Dữ liệu vào

Dòng đầu tiên chứa một xâu có độ dài ~n~.

Dòng tiếp theo chứa một số nguyên ~k~: số lượng mẫu. Cuối cùng, có ~k~ dòng mô tả các mẫu.

Xâu và các mẫu đều gồm các ký tự a–z.

Kết quả

Với mỗi mẫu, in ra số vị trí.

Giới hạn

• ~1 \le n \le 10^5~
• ~1 \le k \le 5 \cdot 10^5~
• tổng độ dài các mẫu tối đa là ~5 \cdot 10^5~

Ví dụ

Dữ liệu vào:

aybabtu
3
bab
abc
a

Kết quả:

1
0
2