직소 퍼즐

다락방을 정리하다가 오래된 게임이 든 상자를 찾았고, 그 안에 직소 퍼즐도 하나 있었다. 아쉽게도 포장이 손상되어 퍼즐 조각 몇 개가 상자 바닥에 흩어져 있고, 일부 조각은 다른 곳에 빠져 있을 수도 있다. 심지어 일부 조각은 전혀 다른 퍼즐에서 나왔을 수도 있다. 지금 눈앞에 퍼즐 조각 더미가 놓여 있고, 이를 맞춰 완성된 퍼즐을 만들어야 한다.

그림 J.1: 첫 번째 예제의 설명도.

좀 더 정확히 말하면 다음과 같다.

• 조각은 n개이며 1부터 n까지 번호가 매겨져 있다. 이 조각들을 나란히 배치해 하나의 직사각형을 만들어야 한다. 모든 조각을 빠짐없이 사용해야 한다.
• 조각의 변은 직선이거나 불규칙한 모양이다. 직선인 변은 직사각형의 가장자리에 놓여야 하고, 불규칙한 변은 안쪽에 놓여야 한다.
• 불규칙한 변의 모양은 모두 다르며, 각 모양은 정확히 두 번씩 나타나고 서로 다른 두 조각에 있다. 두 조각은 맞닿는 변의 모양이 일치할 때만 서로 이웃하게 놓을 수 있다.
• 조각은 회전할 수 있지만, 뒤집을 수는 없다.

첫 줄에 조각의 개수 n (1 이상 3 × 10^5 이하)이 주어진다. 이어지는 n줄에는 각 조각의 연결 상태(변의 모양)가 반시계 방향 순서로 정수 네 개씩 주어진다.

연결 종류 0은 직선 변을 뜻한다. 나머지 연결 종류는 1부터 시작하는 연속된 양의 정수로 번호가 매겨져 있으며, 각 번호는 서로 다른 두 줄에 정확히 두 번씩 나타난다.

위의 조건대로 조각을 맞출 수 없으면 impossible을 출력한다. 그렇지 않으면 완성된 퍼즐을 다음 형식으로 출력한다.

• 격자의 높이 h와 너비 w를 나타내는 정수 두 개를 한 줄에 출력한다 (h, w는 1 이상이고 h × w = n이다).
• 이어서 h줄에 걸쳐, 각 줄마다 w개의 조각 번호를 출력한다.

정답을 어떤 방향으로 회전한 것이든 인정된다.