Дано рядок і шаблони. Знайдіть для кожного шаблону першу позицію (з індексами від 1), де він з’являється в рядку.

Обмеження

• \(1≤n≤10^5\)
• \(1≤k≤5⋅10^5\)
• загальна довжина шаблонів не перевищує \(5 ⋅10^5\)

Формат вхідних даних

У першому рядку вхідних даних є рядок довжиною \(n\).

Наступний рядок містить ціле число \(k\): кількість шаблонів.

Нарешті, є \(k\) рядків, які описують шаблони.

Рядок і шаблони складаються з символів 'a'–'z'.

Формат вихідних даних

Вивести першу позицію для кожного шаблона (або −1, якщо вона взагалі не зустрічається).

Приклад вхідних даних

aybabtu
3
bab
abc
a

Приклад вихідних даних

3
-1
1