Problem Q
String Multimatching

Input

The input consists of at most ten test cases. Each test case begins with an integer $n$ on a line of its own, indicating the number of patterns. Then follow $n$ lines, each containing a non-empty pattern. The total length of all patterns in a test case is no more than $100\, 000$. Then comes a line containing a non-empty text (of length at most $200\, 000$). Input is terminated by end-of-file.

Output

For each test case, output $n$ lines, where the $i$’th line contains the positions of all the occurrences of the $i$’th pattern in text, from first to last, separated by a single space.

2
p
pup
Popup
2
You
peek a boo
you speek a bootiful language
4
anas
ana
an
a
bananananaspaj

2 4
2

5
7
1 3 5 7
1 3 5 7
1 3 5 7 9 12