깊이 순서

물체들을 사진으로 찍으면 이미지가 만들어진다. 이미지는 물체들을 담고 있지만, 물체 공간에 대한 정보의 일부는 이미지에서 사라질 수 있다. 이렇게 사라진 정보를 복원하는 일은 흥미롭고 때로는 까다롭다.

다음 시나리오를 가정한다.

• [A1] 이미지는 $z = -\infty$ 방향에서 직사각형들을 촬영하여 얻는다. 각 직사각형의 변은 $x$축 또는 $y$축과 평행하고, 각 직사각형의 면은 $xy$평면과 평행하다.
• [A2] 직사각형들의 $z$좌표는 모두 다르다. 직사각형들의 깊이 순서는 $1$부터 $n$까지 번호를 매기며, 가장 위(즉 $z$좌표가 가장 작은 것)에 있는 직사각형의 순서가 $1$이다.

각 직사각형의 깊이 정보($z$좌표)는 이미지에 나타나지 않지만, 두 직사각형 중 어느 것이 위에 있는지 추론할 수 있는 경우가 있다(물론 추론할 수 없는 경우도 있다). 예를 들어 그림 1에서는 점선 직사각형 $R_1$이 짙은 색 직사각형 $R_2$ 위에 있음을 쉽게 알 수 있다. 이때 "$R_1$이 $R_2$ 위에 있다", "$R_2$가 $R_1$ 아래에 있다"고 말한다. [A2]에 따르면 $R_1$의 깊이 순서는 $1$, $R_2$의 깊이 순서는 $2$이다.

그림 1

[A1] 때문에 위/아래 관계는 추이적이다. 즉 $R_1$이 $R_2$ 위에 있고 $R_2$가 $R_3$ 위에 있으면 $R_1$이 $R_3$ 위에 있다고 결론지을 수 있다. 그림 2에서는 회색 직사각형 $R_2$가 $R_3$ 위에 있고 $R_1$이 $R_2$ 위에 있으므로, 점선 직사각형 $R_1$이 짙은 색 직사각형 $R_3$ 위에 있다고 결론지을 수 있다. 반면 오른쪽 아래 직사각형 $R_5$에 대해서는 아무 정보도 얻을 수 없다. 이런 경우 $R_5$와 다른 어떤 직사각형 사이의 깊이 순서도 추론할 수 없다고 말한다. 마찬가지로 짙은 색 직사각형 $R_3$와 가로줄로 채워진 직사각형 $R_4$ 사이의 깊이 순서도 추론할 수 없다. [A2]에 따르면 $R_1$의 깊이 순서는 $1$ 또는 $2$, $R_2$는 $2$ 또는 $3$, $R_3$는 $3$, $4$, $5$ 중 하나, $R_4$는 $3$, $4$, $5$ 중 하나, $R_5$는 $1$부터 $5$까지 중 어느 것이든 될 수 있다.

그림 2

모든 이미지가 유효한 것은 아니다. 그림 3은 [A1]과 [A2] 가정 아래에서는 얻을 수 없는 "불가능한" 이미지의 예를 보여준다.

그림 3

이미지 하나와 추가로 직사각형 $\alpha$가 주어진다. 이미지가 [A1]과 [A2] 아래에서 얻을 수 없는 것이면 IMPOSSIBLE을 출력한다. 그렇지 않으면 두 정수 $\beta$와 $\gamma$($\beta \le \gamma$)를 출력한다. 여기서 $\alpha$의 깊이 순서가 가질 수 있는 가장 넓은 범위가 $\beta, \beta+1, \ldots, \gamma$이다.

입력은 $T$개의 테스트 케이스로 이루어진다. 입력의 첫 줄에 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $n$, $N_X$, $N_Y$($2 \le n \le 52$; $2 \le N_X, N_Y \le 80$)가 공백으로 구분되어 주어진다. $n$은 직사각형의 개수이고, $N_X$와 $N_Y$는 각각 이미지의 너비와 높이이다.

이어지는 $N_X$개의 줄에는 각각 $N_Y$개의 픽셀이 공백으로 구분되어 주어진다. 각 픽셀은 배경을 나타내는 기호 $이거나, 직사각형을 나타내는 a, b, ..., z, A, B, ..., Z 중 한 글자이다. 대문자와 소문자는 서로 다른 것으로 구분한다. 가장 작은 직사각형은 $1 \times 1$까지 작을 수 있다.

각 테스트 케이스의 마지막 줄에는 글자 $\alpha$가 주어진다. 이는 깊이 순서의 가장 넓은 범위를 출력해야 하는 직사각형이다.

각 테스트 케이스에 대해, 이미지가 [A1]과 [A2] 아래에서 얻을 수 없는 것이면 한 줄에 IMPOSSIBLE을 출력한다.

그렇지 않으면 두 정수 $\beta$와 $\gamma$($\beta \le \gamma$)를 하나의 공백으로 구분하여 출력한다. 여기서 $\alpha$의 깊이 순서가 가질 수 있는 가장 넓은 범위가 $\beta, \beta+1, \ldots, \gamma$이다.