Under construction

Still being built. Things may change

Label

Time limit2sMemory limit256 MB

Summary
Count the cyclic shifts t of the concatenated label that split into dictionary words separated by one or more dots, and list them.
Level

Hard8 of 10

Topics
String matching, Dynamic programming, Hash map
Solved
No attempts yet

Problem

Archaeologists excavating a settlement of an ancient civilization found a bottle label that has survived to today. This civilization drank from bottles with labels describing the drink, just as people do now. Its writing had no line-break marker. When a line ended, reading simply continued on the next line.

The label wrapped around the bottle as a full cylinder, so the text is read starting from the seam. Reading begins with the first line at the seam. Once the reader reaches the seam, they move to the second line, then the third, and so on. The seam position is unknown. What the scientists have is a set of nn rows, each of the same length kk, made of lowercase letters and the character ., which this civilization used in place of spaces.

The scientists also have a dictionary listing every word the civilization used. Count the non-negative integers t<kt < k such that concatenating all the given rows, then cyclically shifting the result left by tt characters, gives a sequence of dictionary words separated by one or more . characters. Output all such values of tt.

Input

The first line contains one integer mm (1≤m≤20001 \le m \le 2000), the number of words in the dictionary. The next mm lines each contain one dictionary word. All words are distinct, consist only of lowercase Latin letters, and have length at most 2000.

The next line contains one integer nn (1≤n≤20001 \le n \le 2000), the number of rows on the label. The next nn lines contain the rows. Every row consists only of lowercase Latin letters and .. All rows have the same length, at most 2000. Each row contains at least one ..

Output

On the first line, print the number of valid values of tt. On the second line, print all these values in ascending order, separated by spaces.

Examples1

  1. Example 1

    Input
    2
    uu
    u
    5
    .uu..uu
    .uu...u
    ...uu.u
    .u.u.uu
    uuu.uu.
    
    Expected output
    2
    1 2