Word Rolling

Time limit2sMemory limit128 MB

Summary

Given N cyclic letter wheels rotating one step per second, find the earliest time t when all wheels simultaneously display a given target string, using CRT-style reasoning, or report -1.

Level: Hard8 of 10
Topics: Number theory, Math, Combinatorics, Simulation
Solved: No attempts yet

Problem

A display consists of N circular character wheels, and each wheel shows exactly one character at a time. At time 0, every wheel shows the first character of its string. Every second, all wheels rotate forward by one position; after the last character, a wheel returns to its first character.

If the string written on the i-th wheel is S_i, then after t seconds that wheel shows S_i[t mod |S_i|]. Given a target string T, find the smallest time t when the whole display first shows T. If T never appears, output -1.

Input

The first line contains the display size N. N is a positive integer at most 50.

Each of the next N lines contains the string written on one wheel. Each string consists only of uppercase English letters and has length from 3 to 26, inclusive.

The last line contains the target string T. Its length is N, it consists only of uppercase English letters, and no letter appears more than once in T.

Output

Output the first time when the whole display shows T. If there is no such time, output -1. The required answer is at most 9,223,372,036,854,775,807.

Examples4

Example 1
Input
```
3
XYZ
DEF
OPRS
YES
```
Expected output
```
7
```
Example 2
Input
```
2
ABC
ABC
AB
```
Expected output
```
-1
```
Example 3
Input
```
1
ABC
X
```
Expected output
```
-1
```

Example 4

Input

9
CPKHFQEYXVMODNRTSGUBLJ
TJLSURVHFQPAXGCEI
JXNSGADPEWICKLFMVOQ
UOFVKGQIJRECMWXADTPNL
OREWASJFLY
HBEC
ESDRVXCNQUFWKGTOLH
CPLTAMBHYSQDVJIORNW
CG
CAIIEHLQC

Expected output