시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 30 13 13 76.471%

문제

상근이는 빵집에서 일한다. 상근이의 퇴근하기 전에 하는 마지막 업무는 빵을 사장이 원하는 순서대로 정렬하는 것이다.

최근에 상근이는 선영이에게 신기한 기술을 하나 배웠다. 이제 상근이는 기술을 이용해 서로 인접해 있는 빵 세 개를 동시에 주걱으로 던질 수 있다. 놀라운 점은 빵이 땅으로 내려올 때는 가장 오른쪽에 있던 빵이 가장 왼쪽으로 가고, 나머지 빵은 한 칸씩 오른쪽으로 이동하게 된다는 점이다. 즉, 빵의 순서가 [1,2,3,4]일 때, [2,3,4]를 주걱을 이용해서 던지면, 빵이 땅에 내려온 후의 순서는 [1,4,2,3]이 되는 것이다.

이제 상근이가 퇴근할 시간이다. 상근이의 앞에는 지금 빵이 놓여져 있다. 지금 놓여져있는 빵의 순서와 사장이 원하는 순서가 주어졌을 때, 선영이에게 배운 기술만을 사용해서 빵을 정렬할 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 빵의 개수 n (3 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 빵의 현재 순서가 주어지고, 셋째 줄에는 사장이 원하는 빵의 순서가 주어진다. 빵은 1부터 n까지 숫자로 나타낼 수 있다. 두 빵의 번호가 같은 경우는 없다.

출력

만약, 상근이가 선영이에게 배운 기술만을 사용해서 사장이 원하는 순서를 만들 수 있으면 "Possible"을, 불가능하면 "Impossible"을 출력한다.

예제 입력

4
1 3 4 2
4 3 2 1

예제 출력

Possible

예제 입력 2

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

예제 출력 2

Impossible

힌트