Hide

Yraglac recently found a list of compromised passwords for a major online website and would like to analyze the data to find out if any two users have similar passwords. Two passwords are considered similar if they are rotations or reverse rotations of each other. The rotations of a password are formed by repeatedly removing the first letter and appending it to the end. Reverse rotations are the rotations of the reversed password. For example, given the password ABCD:

• Rotations are: ABCD, BCDA, CDAB, DABC

Can you help Yraglac?

Input

The input will contain a single line with $N$, the number of compromised passwords, where $2 \leq N \leq 10^5$. Next will follow $N$ lines with one password per line. Each password will consist only of uppercase letters and will have a length between $1$ and $5\cdot 10^5$ inclusive. The sum of lengths of all passwords will not exceed $10^6$. There may be duplicate passwords in the list. (Since a password is a rotation of itself, the output will always be “Yes” when any password appears twice.)

Output

Output “Yes” if there exists any two passwords that are rotations or reverse rotations of each other, and “No” otherwise.

Sample Input 1 Sample Output 1
3
ABCD
XYZ
CDAB

Yes

Sample Input 2 Sample Output 2
3
ABCD
XYZ

Yes

Sample Input 3 Sample Output 3
3
ABCD
XYZ
ACBD

No

CPU Time limit 10 seconds
Memory limit 1024 MB
Difficulty 7.1Hard
Statistics Show
Author