상자 눕히기

어떤 제조 회사는 제품을 상자에 담아 출고할 때까지 정사각형 창고에 보관한다. 상자는 모두 $1 \times 1 \times z$ 미터인 직육면체이고, $z$는 $1 < z < 30$인 정수다. 처음에는 모든 상자가 긴 변을 세운 채 창고 벽과 나란히 놓여 있어서 상자 하나가 바닥의 한 칸만 차지한다.

창고 관리자는 상자를 세고 확인하려고 상자마다 한 면을 통째로 보고 싶어 한다. 세워 둔 상태에서는 낮은 상자가 높은 상자 뒤에 가려질 수 있으므로, 관리자는 상자를 모두 눕히려고 한다.

창고 바닥은 한 변이 1미터인 칸으로 이루어진 $n \times n$ 격자다. 상자를 눕히는 것은 밑면의 한 모서리를 축으로 상자를 굴리는 것과 같다. 높이가 $z$인 상자를 한 방향으로 눕히면 원래 있던 칸이 비고 그 방향으로 이어지는 $z$칸을 차지한다. 예를 들어 어떤 행이 ..3.....이면 그 상자를 오른쪽으로 눕힌 뒤에는 ...111...이 된다.

상자는 원하는 순서로 하나씩 눕힐 수 있고, 방향도 상자마다 따로 고를 수 있다. 다만 눕는 순간 차지하게 될 $z$칸이 모두 창고 안에 있어야 하고, 그 칸에는 아직 서 있는 상자도 이미 누운 상자도 없어야 한다. 한 번 누운 상자는 그 자리에 그대로 남는다.

상자를 모두 눕힐 수 있는지 판별하시오.

입력은 시나리오 여러 개로 이루어진다. 각 시나리오의 첫 줄에는 창고 한 변의 길이 $n$이 주어진다. ($3 \le n \le 30$)

다음 줄부터는 한 줄에 정수 세 개 $r$, $c$, $z$가 주어지며 각각 상자가 놓인 행, 열, 높이를 뜻한다. ($1 \le r, c \le n$, $1 < z < 30$) 시나리오마다 상자가 하나 이상 있고, 한 칸에 상자가 둘 이상 놓이지는 않는다. 상자 목록은 0 0 0인 줄로 끝난다.

전체 입력은 0 하나만 있는 줄로 끝난다.

시나리오마다 한 줄씩 출력한다. 상자를 모두 눕힐 수 있으면 Possible을, 그렇지 않으면 Impossible을 출력한다.