eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сортировка хлеба

Сортировка хлеба

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Майкл работает в пекарне. В конце смены его босс требует отсортировать хлеб в определенном порядке. Она не может пока определиться в каком порядке, хотя как кажется Майклу, каждый день порядок оказывается новым. Майкл проработал уже в пекарне некоторое время и теперь узнал ловкий трюк с его деревянной хлебобулочной лопаткой. Он может принять три хлеба лежащих рядом друг с другом на лопатку и бросить их в воздухе так, что когда они приземлятся, то самый правый переместится в самую левую позицию, а два других хлеба перейдут на одно место вправо. Другими словами, он может вращаться вправо подпоследовательности хлебов длины три.

Еще до конца смены его коллеги разместили хлеб в длинную линию. Майкл хочет отсортировать хлеба используя трюк с лопаткой. Он может принимать на лопатку любые три последовательных хлеба на линии, вращать их, а затем положить обратно. Иногда даже не имеет значения сколько раз он использует лопатку — если сортировка линии хлеба по требованию босса просто не представляется возможной.

Входные данные

Первая строка содержит целое число n~(3 \le n \le 10^5). Затем следуют две строки: первая строка содержит перестановку чисел от 1 до n, задающих текущий порядок расположений хлебов. Вторая строка содержит перестановку чисел от 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
Источник 2012 Nordic Collegiate Programming Contest, Октябрь 6, Задача B