Ordinamento del pane#6828
Michael lavora in una panetteria. Alla fine di ogni turno, la sua capa pretende che il pane venga disposto in un ordine particolare. Tuttavia, lei non riesce mai a decidere quale debba essere esattamente questo ordine — secondo le osservazioni di Michael, ogni giorno risulta essere diverso.
Michael lavora in panetteria già da un po' di tempo ed è riuscito a padroneggiare un trucco ingegnoso con la sua pala di legno per il pane. Può afferrare con la pala tre pani adiacenti e lanciarli in modo tale che, all'atterraggio, il pane più a destra si ritrovi a sinistra, mentre gli altri due si spostano di una posizione verso destra. In altre parole, può eseguire uno spostamento ciclico verso destra per qualsiasi sottosequenza di tre pani consecutivi.
Prima della fine del turno, i suoi colleghi hanno già disposto il pane in un'unica lunga fila. Michael vuole ordinare il pane usando il suo trucco con la pala. Può prendere tre pani consecutivi qualsiasi nella fila, ruotarli nel modo descritto e poi rimetterli al loro posto. Tuttavia, a volte non importa quante volte usi la pala — non è comunque possibile ordinare il pane nell'ordine richiesto dalla capa.
La prima riga contiene un numero intero n~(3 \le n \le 10^5). Seguono poi due righe:
la prima contiene una permutazione dei numeri da a , che indica l'ordine attuale dei pani;
la seconda riga contiene una permutazione dei numeri da a , che indica l'ordine dei pani richiesto dalla capa.
Stampate "Possible" se Michael riesce, usando la sua pala, a ordinare il pane come richiesto dalla capa. In caso contrario, stampate "Impossible".
Esempio 1
Esempio 2