Given an integer n indicating the number of patterns.Then follow n lines, each containing non empty strings, representing patterns. Then comes a non empty string representing text. Output n lines where ith line contains the positions of all occurances of the ith pattern in text.
Input Format
First line: n Then follow n lines, each containing non empty strings, representing patterns. Next line consists of a string, text
Output Format
Print n lines each consisting of occurrences of ith pattern's start index , print -1 if ith pattern doesnt occur
Constraints
|pattern| < 10^5 |text| < 10^5
Example
Input
6 ACC ATC CAT GCG C T GCATCG
Output
-1 2 1 -1 1 4 3