Bread Sorting#6828
Michael works in a bakery. At the end of each shift, his boss asks him to sort the loaves of bread in a certain order. However, she cannot decide exactly what that order should be — according to Michael's observations, it seems to be different every day.
Michael has been working at the bakery for some time and has learned a clever trick with his wooden bread paddle. He can scoop up three adjacent loaves with the paddle and toss them into the air so that when they land, the rightmost loaf moves to the leftmost position, while the other two loaves shift one position to the right. In other words, he can perform a cyclic right rotation on any subsequence of three consecutive loaves.
Before the end of the shift, his colleagues have already placed the bread in one long line. Michael wants to sort the loaves using his paddle trick. He can pick up any three consecutive loaves in the line, rotate them as described, and put them back. However, sometimes it does not matter how many times he uses the paddle — sorting the bread into the order required by his boss may simply be impossible.
The first line contains an integer n~(3 \le n \le 10^5). Then two lines follow:
the first line contains a permutation of the integers from to , representing the current order of the loaves.
the second line contains a permutation of the integers from to , representing the order of the loaves required by the boss.
Print "Possible" if Michael can use his paddle to sort the loaves into the order required by his boss. Otherwise, print "Impossible".
Example 1
Example 2