Harry Potter and His Magic Scroll

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2664
64-bit integer IO format: %I64d      Java class name: Main

Description

Harry Potter want to make some scrolls to improve his magic power. He has a very big incantation dictionary, and the content of a scroll, must be a continuous passage from the dictionary. To make the scroll more powerful, Harry pick out a few powerful magic words, and want the scroll contains them. Given such magic words, where to start and where to end, to make the total number of words Harry Potter must write down for a scroll minimum? If there are some passages whose length are equal, choose the one which start first.

Input

The first line is the number of cases.
For each case, there will be the content of the dictionary, which end with a line contains a single "#". Each line of the dictionary will not contain more than 2,000 characters, ant it will contain no more than 100,000 words. In a dictionary, Words are only splited by a single space. A word MAY in two lines.
Then followed by a line contain a integer T, indicates the number of scrolls. For each scroll, First line is an integer m meaning the number of magic words that the scroll must contain, then followed by m such magic words. The length of a word will not exceed 20.

Output

For each scroll, output the start dictionary character position(start from 0) and the end of it.

Sample Input

1 
Harr 
y Potter want to make some scrolls to improve his magic power. 
# 
2 
2 
Harry 
Potter 
1 
to

Sample Output

0 11 
18 19

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .