Сортировка хлеба#6828
Майкл работает в пекарне. В конце каждой смены его босс требует отсортировать хлеб в определённом порядке. Однако она никак не может решить, каким именно должен быть этот порядок — по наблюдениям Майкла, каждый день он оказывается новым.
Майкл уже некоторое время работает в пекарне и успел освоить хитрый трюк со своей деревянной хлебной лопаткой. Он может подхватить лопаткой три соседних хлеба и подбросить их так, что при приземлении самый правый хлеб окажется слева, а два остальных сдвинутся на одну позицию вправо. Иными словами, он может выполнять циклический сдвиг вправо для любой подпоследовательности из трёх соседних хлебов.
Перед окончанием смены его коллеги уже выложили хлеб в одну длинную линию. Майкл хочет отсортировать хлеб, используя свой трюк с лопаткой. Он может брать любые три последовательных хлеба на линии, вращать их описанным образом и затем класть обратно. Однако иногда не имеет значения, сколько раз он воспользуется лопаткой — отсортировать хлеб в требуемом боссом порядке всё равно невозможно.
Первая строка содержит целое число n~(3 \le n \le 10^5). Затем следуют две строки:
первая содержит перестановку чисел от до , задающую текущий порядок хлебов;
вторая строка содержит перестановку чисел от до , задающую порядок хлебов, требуемый боссом.
Выведите "Possible", если Майкл сможет с помощью своей лопатки отсортировать хлеб так, как требует босс. В противном случае выведите "Impossible".
Example 1
Example 2