Shiritori

Interview

Time limit2sMemory limit1024 MB

Summary

Given words called in a Shiritori game, find the first player who breaks the rule of starting with the previous word's last letter or reusing a word.

Level: Easy3 of 10
Topics: String, Hash map
Solved: No attempts yet

Problem

The original version of Shiritori is played with Japanese hiragana, katakana, or kanji characters. Source WikiMedia

The Japanese game of Shiritori is well suited to a long car ride. The rules are simple. The first player says any word. The second player must then say a new word that begins with the last letter of the word the first player just said. Given the history of words used in a game, determine whether the game was played according to these rules. Player 1 always starts first.

Input

One test case is given. The first line contains an integer $N$ ( $2 \leq N \leq 100\,000$ ). Each of the following $N$ lines contains one word. The words are listed in the order the players called them out, starting with player 1. Every word consists of between 1 and 120 lowercase English letters.

Output

If the game was played according to the rules, print Fair Game. Otherwise, find the player who first violated the rules, and print Player <i> lost. That player loses the game. For example, if player 1 violated the rules first, print Player 1 lost.

Examples4

Example 1

Input

5
apple
ear
real
letters
style

Expected output

Fair Game

Example 2
Input
```
3
apple
extra
apple
```
Expected output
```
Player 1 lost
```
Example 3
Input
```
2
apple
neat
```
Expected output
```
Player 2 lost
```

Example 4

Input

5
apple
east
team
meat
team

Expected output

Player 1 lost