Сортування хліба#6828
Майкл працює в пекарні. Наприкінці кожної зміни його бос вимагає відсортувати хліб у певному порядку. Однак вона ніяк не може вирішити, яким саме має бути цей порядок — за спостереженнями Майкла, щодня він виявляється новим.
Майкл вже деякий час працює в пекарні і встиг опанувати хитрий трюк зі своєю дерев'яною хлібною лопаткою. Він може підхопити лопаткою три сусідні хліби і підкинути їх так, що при приземленні найправіший хліб опиниться зліва, а два інших зсунуться на одну позицію вправо. Іншими словами, він може виконувати циклічний зсув вправо для будь-якої підпослідовності з трьох сусідніх хлібів.
Перед закінченням зміни його колеги вже викладили хліб в одну довгу лінію. Майкл хоче відсортувати хліб, використовуючи свій трюк з лопаткою. Він може брати будь-які три послідовні хліби на лінії, обертати їх описаним чином і потім класти назад. Однак іноді не має значення, скільки разів він скористається лопаткою — відсортувати хліб у порядку, який вимагає бос, всі одно неможливо.
Перший рядок містить ціле число n~(3 \le n \le 10^5). Далі йдуть два рядки:
перший містить перестановку чисел від до , що задає поточний порядок хлібів;
другий рядок містить перестановку чисел від до , що задає порядок хлібів, який вимагає бос.
Виведіть "Possible", якщо Майкл зможе за допомогою своєї лопатки відсортувати хліб так, як вимагає бос. У протилежному випадку виведіть "Impossible".
Приклад 1
Приклад 2