시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB76234024157.109%

문제

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

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

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

입력

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

출력

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

예제 입력 1

4
1 3 4 2
4 3 2 1

예제 출력 1

Possible

예제 입력 2

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

예제 출력 2

Impossible
W3sicHJvYmxlbV9pZCI6IjUwMDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNzUgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViZTc1XHVjOWQxXHVjNWQwXHVjMTFjIFx1Yzc3Y1x1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1ZDFmNFx1YWRmY1x1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVkNTU4XHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWM1YzVcdWJiMzRcdWIyOTQgXHViZTc1XHVjNzQ0IFx1YzBhY1x1YzdhNVx1Yzc3NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzJlMFx1YWUzMFx1ZDU1YyBcdWFlMzBcdWMyMjBcdWM3NDQgXHVkNTU4XHViMDk4IFx1YmMzMFx1YzZlMFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFlMzBcdWMyMjBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YzExY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHViMjk0IFx1YmU3NSBcdWMxMzggXHVhYzFjXHViOTdjIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM4ZmNcdWFjNzFcdWM3M2NcdWI4NWMgXHViMzU4XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjE4MFx1Yjc3Y1x1YzZiNCBcdWM4MTBcdWM3NDAgXHViZTc1XHVjNzc0IFx1YjU0NVx1YzczY1x1Yjg1YyBcdWIwYjRcdWI4MjRcdWM2MmMgXHViNTRjXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMzU4IFx1YmU3NVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjIFx1YWMwMFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1YmU3NVx1Yzc0MCBcdWQ1NWMgXHVjZTc4XHVjNTI5IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0XHViMjk0IFx1YzgxMFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWJlNzVcdWM3NTggXHVjMjFjXHVjMTFjXHVhYzAwIFsxLDIsMyw0XVx1Yzc3YyBcdWI1NGMsIFsyLDMsNF1cdWI5N2MgXHVjOGZjXHVhYzcxXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWIzNThcdWM5YzBcdWJhNzQsIFx1YmU3NVx1Yzc3NCBcdWI1NDVcdWM1ZDAgXHViMGI0XHViODI0XHVjNjI4IFx1ZDZjNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIyOTQgWzEsNCwyLDNdXHVjNzc0IFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzgxYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVkMWY0XHVhZGZjXHVkNTYwIFx1YzJkY1x1YWMwNFx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzU1ZVx1YzVkMFx1YjI5NCBcdWM5YzBcdWFlMDggXHViZTc1XHVjNzc0IFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YWUwOCBcdWIxOTNcdWM1ZWNcdWM4MzhcdWM3ODhcdWIyOTQgXHViZTc1XHVjNzU4IFx1YzIxY1x1YzExY1x1YzY0MCBcdWMwYWNcdWM3YTVcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHViYzMwXHVjNmI0IFx1YWUzMFx1YzIyMFx1YjljY1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHViZTc1XHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZTc1XHVjNzU4IFx1YWMxY1x1YzIxOCBuICgzICZsZTsgbiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJlNzVcdWM3NTggXHVkNjA0XHVjN2FjIFx1YzIxY1x1YzExY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjN2E1XHVjNzc0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWJlNzVcdWM3NTggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViZTc1XHVjNzQwIDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWJlNzVcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljY1x1YzU3ZCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWJjMzBcdWM2YjQgXHVhZTMwXHVjMjIwXHViOWNjXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWMwYWNcdWM3YTVcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCAmcXVvdDtQb3NzaWJsZSZxdW90O1x1Yzc0NCwgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViYTc0ICZxdW90O0ltcG9zc2libGUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjUwMDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCcmVhZCBTb3J0aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5NaWNoYWVsIHdvcmtzIGluIGEgYmFrZXJ5LiBBdCB0aGUgZW5kIG9mIGhpcyBzaGlmdCwgaGlzIGJvc3Mgd2FudHMgdGhlIGJyZWFkcyBzb3J0ZWQgaW4gYSBjZXJ0YWluIG9yZGVyLiBTaGUgY2FuJnJzcXVvO3Qgc2VlbSB0byBkZWNpZGUgb24gd2hpY2ggb3JkZXIsIHRob3VnaCAmbmRhc2g7IGV2ZXJ5IGRheSB0aGVyZSBzZWVtcyB0byBiZSBhIG5ldyBvbmUgJm5kYXNoOyB0byBNaWNoYWVsJnJzcXVvO3MgZGVzcGFpci4gTWljaGFlbCBoYXMgd29ya2VkIHRoZXJlIGZvciBhIHdoaWxlIG5vdyBhbmQgaGFzIGxlYXJuZWQgYSBuZWF0IHRyaWNrIHdpdGggaGlzIHdvb2RlbiBiYWtlcnkgcGFkZGxlLiBIZSBjYW4gdGFrZSB0aHJlZSBicmVhZHMgbmV4dCB0byBlYWNoIG90aGVyIG9uIGhpcyBwYWRkbGUgYW5kIHRocm93IHRoZW0gdXAgaW4gdGhlIGFpciBzdWNoIHRoYXQgd2hlbiB0aGV5IGxhbmQsIHRoZSByaWdodC1tb3N0IGhhcyBtb3ZlZCB0byB0aGUgbGVmdC1tb3N0IHBvc2l0aW9uLCBhbmQgdGhlIHR3byBvdGhlciBicmVhZHMgaGF2ZSBtb3ZlZCBvbmUgcGxhY2UgdG8gdGhlIHJpZ2h0LiBJbiBvdGhlciB3b3JkcywgaGUgY2FuIHJvdGF0ZSB0byB0aGUgcmlnaHQgYSBzdWJzZXF1ZW5jZSBvZiBicmVhZHMgb2YgbGVuZ3RoIHRocmVlLjxcL3A+XHJcblxyXG48cD5CZWZvcmUgdGhlIGVuZCBvZiB0aGUgc2hpZnQsIGhpcyBjb3dvcmtlcnMgcGxhY2UgdGhlIGJyZWFkcyBpbiBhIGxvbmcgbGluZS4gTWljaGFlbCB3b3VsZCBsaWtlIHRvIHNvcnQgdGhlIGxpbmUgb2YgYnJlYWRzIHVzaW5nIGhpcyBwYWRkbGUgdHJpY2suIEhlIGNhbiB0YWtlIGFueSB0aHJlZSBjb25zZWN1dGl2ZSBicmVhZHMgYWxvbmcgdGhlIGxpbmUgb24gaGlzIHBhZGRsZSwgcm90YXRlIHRoZW0sIGFuZCB0aGVuIHB1dCB0aGVtIGJhY2suIFNvbWV0aW1lcyB0aG91Z2gsIGl0IGRvZXMgbm90IG1hdHRlciBob3cgbWFueSB0aW1lcyBoZSB1c2VzIGhpcyBwYWRkbGUgJm5kYXNoOyB0aGUgbGluZSBvZiBicmVhZCBqdXN0IGRvZXNuJnJzcXVvO3Qgc2VlbSB0byBiZSBwb3NzaWJsZSB0byBzb3J0IHRoZSB3YXkgdGhlIGJvc3Mgd2FudHMuLi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgbiwgMyAmbGU7IG4gJmxlOyAxMDAgMDAwLiBUaGVuIHR3byBsaW5lcyBmb2xsb3c6IE9uIHRoZSBcdWZiMDFyc3QgbGluZSwgYSBwZXJtdXRhdGlvbiBvZiB0aGUgaW50ZWdlcnMgMSB0aHJvdWdoIG4gZGVzY3JpYmluZyB0aGUgb3JkZXIgaW4gd2hpY2ggdGhlIGJyZWFkcyBhcmUgbGluZWQgdXAuIE9uIHRoZSBzZWNvbmQgbGluZSwgYSBwZXJtdXRhdGlvbiBvZiB0aGUgaW50ZWdlcnMgMSB0aHJvdWdoIG4gZGVzY3JpYmluZyBob3cgTWljaGFlbCZyc3F1bztzIGJvc3Mgd2FudHMgdGhlIGJyZWFkcyBzb3J0ZWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCAmbGRxdW87UG9zc2libGUmcmRxdW87IGlmIE1pY2hhZWwgY2FuIHNvcnQgdGhlIGJyZWFkcyB3aXRoIGhpcyBwYWRkbGUgaW4gdGhlIG9yZGVyIHByZXNjcmliZWQgYnkgaGlzIGJvc3MsIG90aGVyd2lzZSAmbGRxdW87SW1wb3NzaWJsZSZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=