Special Homework Reordering

Time limit1sMemory limit1024 MB

Summary

Decide whether a permutation can be turned into a target permutation by repeatedly sorting any three adjacent elements in ascending or descending order.

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

Problem

Mr Singh is a teacher at NLCS Jeju. He is planning lessons for 12th graders who are struggling with the IB program.

Mr Singh made a homework plan, which is the order in which students receive their homework. The plan has $N$ assignments, and each assignment has a unique number from 1 to $N$ .

Students saw the plan and got angry. They submitted a requested homework order to the teacher.

Mr Singh agreed to consider the students' request, but he does not want to ruin the curriculum. He wants to know whether he can turn the original plan into the requested order by repeating the following operation any number of times.

Choose 3 adjacent assignments and sort them in ascending or descending order by assignment number.

Write a program that checks whether Mr Singh can turn the original plan into the requested order by repeating this operation any number of times.

Input

The first line contains $N$ .

The second line contains the original homework plan. It is given as $N$ distinct integers separated by spaces, and every integer is between 1 and $N$ .

The third line contains the requested order in the same format as the second line.

Output

On the first line, print POSSIBLE if Mr Singh can turn the original plan into the requested order by repeating the operation any number of times. Otherwise, print IMPOSSIBLE. The output is case-sensitive.

Constraints

$3 \leq N \leq 100\,000$

Examples2

Example 1
Input
```
5
5 4 3 1 2
1 2 3 4 5
```
Expected output
```
POSSIBLE
```
Example 2
Input
```
5
1 2 3 4 5
1 4 2 5 3
```
Expected output
```
IMPOSSIBLE
```