와플 자르기

인피니트 하우스 오브 팬케이크의 손님들은 원형 팬케이크에 싫증이 났고, 이에 요리사들은 새로운 메뉴인 와플을 선보이려 한다! 홍보 행사로, 요리사들은 R개의 행과 C개의 열로 이루어진 정사각형 칸 격자 모양의 커다란 와플 하나를 만들었다. 와플의 각 칸은 비어 있거나 초콜릿 칩 하나를 담고 있다.

이제 요리사들이 배고픈 손님들에게 와플을 나누어 줄 차례이다. 가로 절단은 두 행 사이의 격자선 전체를 따라 이루어지고, 세로 절단은 두 열 사이의 격자선 전체를 따라 이루어진다. 효율을 위해 한 요리사는 정확히 H개의 서로 다른 가로 절단을 하고, 다른 요리사는 정확히 V개의 서로 다른 세로 절단을 한다. 그러면 편리하게도 (H + 1) × (V + 1)명의 손님 각각에게 한 조각씩 돌아간다. 모든 조각의 크기가 반드시 같지는 않지만, 이는 괜찮다. 시장 조사에 따르면 손님들은 조각의 크기를 신경 쓰지 않는다.

손님들이 신경 쓰는 것은 자신이 받는 초콜릿 칩의 개수이므로, 각 조각에는 정확히 같은 수의 초콜릿 칩이 있어야 한다. 주어진 가로 및 세로 절단 횟수를 사용하여 요리사들이 이 목표를 달성할 수 있는지 판별하라.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 6초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

2 ≤ R ≤ 10. 2 ≤ C ≤ 10. H = 1. V = 1.

테스트 세트 2 (비공개)

2 ≤ R ≤ 100. 2 ≤ C ≤ 100. 1 ≤ H < R. 1 ≤ V < C.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어지며, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 네 정수 R, C, H, V가 포함된 한 줄로 시작한다. 이들은 각각 와플의 행 수와 열 수, 그리고 요리사들이 해야 하는 정확한 가로 절단 횟수와 세로 절단 횟수를 나타낸다. 그다음에는 각각 C개의 문자로 이루어진 R개의 줄이 더 주어진다. 이 줄들 중 i번째 줄의 j번째 문자는 와플의 i번째 행과 j번째 열에 있는 칸을 나타낸다. 각 문자는 그 칸에 초콜릿 칩이 있음을 뜻하는 @이거나, 그 칸이 비어 있음을 뜻하는 .이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(시작 번호는 1), y은 요리사들이 위에서 설명한 목표를 달성할 수 있으면 POSSIBLE, 달성할 수 없으면 IMPOSSIBLE이다.

마지막 두 예제 케이스는 테스트 세트 1에 등장하지 않는다는 점에 유의하라.

예제 케이스 #1에서 가능한 전략 중 하나는 위에서 두 번째 행과 세 번째 행 사이를 가로로 자르고, 왼쪽에서 네 번째 열과 다섯 번째 열 사이를 세로로 자르는 것이다. 그러면 다음과 같은 조각들이 만들어지며, 각 조각에는 정확히 두 개의 초콜릿 칩이 있다.

` .@@. .@ .... .@

@.@. @@ `

예제 케이스 #2에서는 가로 절단과 세로 절단을 어디에 하더라도 초콜릿 칩의 수가 서로 다른 조각들이 만들어지므로 불가능하다.

예제 케이스 #3에서는 와플에 초콜릿 칩이 하나도 없다. 어떤 절단 전략을 사용해도 조각마다 초콜릿 칩의 수가 모두 같으므로(영 개), 손님들은 행복해한다... 하지만 초콜릿 칩을 받았을 때만큼 행복하지는 않을지도 모른다!

예제 케이스 #4에서는 예제 케이스 #2에서와 마찬가지로 가로 절단과 세로 절단을 어디에 하더라도 성공할 수 없다.

예제 케이스 #5에서 요리사들은 가능한 단 두 개의 가로 절단을 모두 하고, 첫 번째 열과 세 번째 열의 오른쪽에서 두 번 세로로 자를 수 있다.

예제 케이스 #6는 가로 및 세로 절단 횟수가 달랐다면 가능했겠지만, 반드시 정확히 H번 가로로 자르고 정확히 V번 세로로 잘라야 한다는 점을 기억하라. 한 번의 가로 절단과 두 번의 세로 절단을 어디에 하더라도 성공할 수 없다.