Snowflakes

Time limit1sMemory limit128 MB

Summary

Given up to 100,000 snowflakes of six arm lengths each, find whether two are identical under cyclic rotation or reversal.

Level: Medium5 of 10
Topics: Hash map, String, Sorting, Implementation
Solved: No attempts yet

Problem

You may have heard that no two snowflakes are alike. Your task is to write a program that determines whether this is really true. Your program reads information about a collection of snowflakes and searches for a pair that may be identical.

Each snowflake has six arms. For each snowflake you are given the length of each of its six arms. Any pair of snowflakes whose corresponding arm lengths all match should be flagged as possibly identical.

Two snowflakes are considered identical if the arm lengths of one can be read, starting from some arm and going in one direction (clockwise or counterclockwise), so that they exactly match the other. In other words, two snowflakes match if one arm-length sequence is a cyclic rotation of the other, or a cyclic rotation of the other reversed.

Input

The first line contains a single integer $n$ ( $0 < n \le 100000$ ), the number of snowflakes. Each of the next $n$ lines describes one snowflake with six integers, the lengths of its arms, where each length is at least $0$ and less than $10000000$ . The lengths are given in the order the arms appear around the snowflake (either clockwise or counterclockwise), but the list may begin with any of the six arms. For example, the same snowflake could be described as 1 2 3 4 5 6 or 4 3 2 1 6 5.

Output

If all of the snowflakes are distinct, print:

No two snowflakes are alike.

If there is a pair of possibly identical snowflakes, print:

Twin snowflakes found.

Examples3

Example 1

Input

2
1 2 3 4 5 6
4 3 2 1 6 5

Expected output

Twin snowflakes found.

Example 2

Input

1
1 2 3 4 5 6

Expected output

No two snowflakes are alike.

Example 3

Input

2
1 2 3 4 5 6
3 4 5 6 1 2

Expected output

Twin snowflakes found.