Bình có một văn bản \(T\) và \(K\) từ khóa. Bình muốn đếm số lần mỗi từ khóa xuất hiện trong \(T\) (các lần xuất hiện có thể chồng lấn). Hãy giúp Bình!

Định dạng đầu vào

• Dòng đầu: xâu \(T\) (\(1 \le |T| \le 10^5\)), gồm chữ cái in thường a..z.
• Dòng hai: số nguyên \(K\) (\(1 \le K \le 10^5\)).
• \(K\) dòng tiếp theo: mỗi dòng là một từ khóa, tổng độ dài không quá \(10^5\).

Định dạng đầu ra

• In ra \(K\) dòng, dòng thứ \(i\) là số lần từ khóa thứ \(i\) xuất hiện.

Ví dụ

Input:

aaaaa
3
a
aa
aaa

Output:

5
4
3

Ràng buộc