Hide

Problem G
Password Rotation

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

  • Reverse rotations are: DCBA, CBAD, BADC, ADCB

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
CBAD
Yes
Sample Input 3 Sample Output 3
3
ABCD
XYZ
ACBD
No

Please log in to submit a solution to this problem

Log in