Dictionaries

The task

You are given several dictionaries, each of them consisting of nonempty words over the alphabet 'a',..,'z', and a text over the same alphabet. Your task is to find the shortest substring (a continuous subsequence of characters) of the text which contains (as its substrings) at least one word from each dictionary. If there are more feasible substrings of the minimal length, we search for that one with the smallest start index.

Input

The first line of the input contains a text to be processed. The second line contains an integer D which is the number of dictionaries. The remaining lines represent dictionaries. Representation of a dictionary starts by a line containing integer N which gives the number of words in the dictionary. The words are written in the next N lines, one word per line, in an arbitrary order.
A word can be contained in several dictionaries. Each dictionary contains at least one word and all its words are distinct. The text length is not greater than 3 × 106, the number of dictionaries does not exceed 2000, the sum of dictionaries sizes (where dictionary size is the number of words in the dictionary) does not exceed 8000. Each word has at most 20 characters. It is guaranteed that the input text contains at least one word from each dictionary as its substring.

Output

Let the searched optimal substring be of length L, starting at position P (note that the first character of the text is at position 0). The output consists of two lines where the first line contains P and the second line contains L.

Example 1

Input
jelenovipivonelej
2
3
jelen
jel
pivo
3
lej
jen
pito
Output
8
9
The searched substring is the suffix 'pivonelej', containing 'pivo' from the first dictionary and 'lej' from the second dictionary.

Example 2

Input
kralsekalakapralkafral
3
3
kral
lak
sekat
3
pral
a
kral
2
prak
kal
Output
6
5
The searched substring is 'kalak', starting at position 6. It contains 'lak', 'a' and 'kal', which are words from all three dictionaries.

Example 3

Input
kolkolemdokolenolemokolopolendopoleprolen
4
4
koleno
poleno
soleno
pro
3
len
lem
dok
2
role
kolem
5
kolem
len
polen
mok
pro
Output
35
6
The searched substring is the suffix 'prolen'.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set