Clock Photos

Interview

Time limit1sMemory limit256 MB

Summary

Decide whether two sets of hand angles on a dial coincide after rotating one photo.

Level: Medium5 of 10
Topics: Sorting, String matching
Solved: No attempts yet

Problem

Sanggeun has two photos of an unusual clock. The clock has $n$ hands, all of the same length and the same purpose. The numbers on the dial have faded away, so the only thing left to tell apart is the position of each hand.

Sanggeun wants to know whether the two photos show the same time, so he plans to rotate each photo by an angle of his own choosing. A photo may be rotated, but it may not be flipped over. If rotating one photo puts its hands exactly on the positions of the other photo's hands, with none left over, the two photos show the same time.

Given the hand positions in both photos, decide whether the two photos can show the same time.

Input

The first line contains the number of hands $n$ ( $2 \le n \le 200000$ ).

Each of the next two lines contains $n$ integers. Each integer $a_i$ ( $0 \le a_i < 360000$ ) is the clockwise angle of one hand in that photo, where a full turn is 360000. The angles come in no particular order, and no angle appears twice on the same line, so the hands of one clock all point in different directions.

Output

Print possible if the two photos can show the same time, and impossible otherwise.

Examples4

Example 1
Input
```
6
1 2 3 4 5 6
7 6 5 4 3 1
```
Expected output
```
impossible
```
Example 2
Input
```
2
0 270000
180000 270000
```
Expected output
```
possible
```

Example 3

Input

7
140 130 110 120 125 100 105
235 205 215 220 225 200 240

Expected output

impossible

Example 4
Input
```
2
0 1
1 0
```
Expected output
```
possible
```