Bread Sorting

Interview

Time limit1sMemory limit128 MB

Summary

Decide whether one permutation of 1..n can be turned into another using only the operation that rotates any three adjacent elements right by one.

Level: Medium6 of 10
Topics: Array, Greedy, Sorting, Math
Solved: No attempts yet

Problem

Sanggeun works at a bakery. His last task before leaving for the day is to arrange the loaves of bread in the order his boss wants.

Sanggeun can use a special trick to toss three adjacent loaves at once with a spatula. When the loaves land again, the rightmost of the three moves to the leftmost spot, while the other two each shift one position to the right. In other words, applying the trick to three loaves $[a, b, c]$ turns them into $[c, a, b]$ . For example, if the order is $[1, 2, 3, 4]$ and the trick is applied to $[2, 3, 4]$ at positions $2, 3, 4$ , the order becomes $[1, 4, 2, 3]$ .

Given the current order of the loaves and the order the boss wants, write a program that decides whether the desired order can be reached using only this trick.

Input

The first line contains the number of loaves $n$ $(3 \le n \le 100{,}000)$ . The second line gives the current order of the loaves, and the third line gives the order the boss wants, each separated by spaces. The loaves are labeled with distinct integers from $1$ to $n$ ; no two loaves share a label.

Output

Print Possible if the boss's desired order can be produced using only the trick, or Impossible otherwise.

Examples2

Example 1
Input
```
4
1 3 4 2
4 3 2 1
```
Expected output
```
Possible
```
Example 2
Input
```
6
1 2 3 4 5 6
6 5 4 3 2 1
```
Expected output
```
Impossible
```