Box Toppling

A manufacturer packs its goods into boxes and stores them in a square warehouse until they are delivered. Every box measures $1 \times 1 \times z$ metres, where $z$ is an integer with $1 < z < 30$. At the start every box stands on end, so it covers a single square of the warehouse floor, and its sides run parallel to the walls.

The foreman wants to see one whole face of every box so that he can count and identify them. While the boxes stand on end a short box may be hidden behind one or more tall boxes, so he wants every box laid flat.

The floor is an $n \times n$ grid of one metre squares. Toppling a box rotates it about a bottom edge: the box leaves the square it stood on and covers the next $z$ squares in the direction it falls. A row that reads ..3..... becomes ...111... once that box topples to the right.

You may topple the boxes one at a time in any order, and you may pick the direction of each box separately. A box topples only if the $z$ squares it lands on are inside the warehouse and empty at that moment, holding neither a box that still stands nor a box that already lies flat. A box that lies flat stays where it is.

Decide whether every box can be laid flat.

The input holds several scenarios. The first line of each scenario holds the side length of the warehouse, $n$. ($3 \le n \le 30$)

Each of the following lines holds three integers $r$, $c$ and $z$: the row, the column and the height of one box. ($1 \le r, c \le n$, $1 < z < 30$) Every scenario holds at least one box, and no two boxes stand on the same square. The list of boxes ends with a line reading 0 0 0.

A line holding the single number 0 ends the input.

Print one line for each scenario. Print Possible if every box can be laid flat, and Impossible otherwise.