An Unfair Puzzle

Interview

Time limit2sMemory limit256 MB

Summary

Given two permutations of 1..n, decide whether cyclic rotations and reversals can turn the first into the second, printing good puzzle or bad puzzle.

Level: Medium6 of 10
Topics: String, String matching, Two pointers, Implementation
Solved: No attempts yet

Problem

Hyunwook likes puzzle games. One day a friend recommended a small flash puzzle game with the following rules.

The player starts with one sequence in which every number from 1 to $n$ appears exactly once.
Another sequence in which every number from 1 to $n$ appears exactly once is given as the goal. The player has to transform the starting sequence into that goal sequence.
The player has two moves, and each move can be performed any number of times.
- Flip: reverse the order of the current sequence. For example, 1 2 3 4 5 becomes 5 4 3 2 1.
- Shift: move the current sequence one place to the left or to the right. The number pushed off one end comes back at the other end. For example, shifting 1 2 3 4 5 one place to the right gives 5 1 2 3 4.

The rules are simple, but the puzzle would not come out. After a long time Hyunwook compared the two sequences again and realised that the goal sequence can never be built with the given moves.

Angry about it, Hyunwook decided to write a program that decides whether a given puzzle is a fair one, so that he can take the matter to the puzzle author. Help him deal with the author.

Input

The first line contains $n$ ( $1 \le n \le 10^6$ ).

The second line contains the starting sequence: the numbers 1 to $n$ , each exactly once, separated by spaces.

The third line contains the goal sequence in the same format.

Output

Print good puzzle if the starting sequence can be turned into the goal sequence using only the two given moves, and bad puzzle otherwise.

Examples7

Example 1
Input
```
5
1 2 3 4 5
4 3 2 1 5
```
Expected output
```
good puzzle
```
Example 2
Input
```
5
1 2 3 4 5
1 2 4 3 5
```
Expected output
```
bad puzzle
```
Example 3
Input
```
1
1
1
```
Expected output
```
good puzzle
```
Example 4
Input
```
2
1 2
2 1
```
Expected output
```
good puzzle
```
Example 5
Input
```
3
1 2 3
1 3 2
```
Expected output
```
good puzzle
```
Example 6
Input
```
6
4 1 6 2 5 3
4 1 6 2 5 3
```
Expected output
```
good puzzle
```

Example 7

Input

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

Expected output

good puzzle