Дано рядок та набір шаблонів, визначте для кожного шаблону кількість позицій, на яких він зустрічається в рядку.
Перший рядок містить рядок довжини n~(1 \le n \le 10^5).
Другий рядок містить ціле число k~(1 \le k \le 5 \cdot 10^5) — кількість шаблонів. Кожен з наступних рядків містить один шаблон. Сумарна довжина всіх шаблонів не перевищує 5 \cdot 10^5.
Рядок та шаблони складаються з малих латинських літер '' - ''.
Для кожного шаблону виведіть на окремому рядку кількість його входжень у рядок.
Приклад 1