동맹

판타지 세계에 직사각형 모양의 큰 섬이 있다. 섬의 두 변의 길이는 각각 정확히 R마일, C마일이며, 섬 전체는 격자 형태의 구역들로 나뉜다. 일부 구역에는 아무도 살지 않고, 나머지 구역에는 판타지 종족의 마을이 있다: 엘프, 인간, 드워프, 호빗. 각 구역에는 마을이 최대 하나 있다. 두 마을이 변을 공유하는 구역에 있으면 이웃이라고 한다.

최근 마을들은 거대한 악(Great Evil)을 두려워하게 되었다. 더 안전하다고 느끼기 위해, 각 마을은 이웃 중 일부와 군사 동맹을 맺기로 했다. 하나의 동맹은 항상 이웃한 두 마을 사이에서 맺어지며, 상호적이고 대칭적인 합의다.

마을에 사는 종족에 따라, 주민들은 특정한 동맹 구성이 이루어지지 않으면 안전하다고 느끼지 않는다:

• 엘프는 자신감이 있어 정확히 1개의 동맹이 필요하다.
• 인간 마을은 정확히 2개의 이웃과 동맹이 필요하다. 게다가 마을의 서로 마주 보는(반대편) 두 변을 노출시키는 것은 전술적으로 나쁘다. 따라서 동맹을 맺는 두 이웃은 마을의 반대편에 위치할 수 없다. (즉, 위·아래 또는 왼쪽·오른쪽처럼 마주 보는 두 방향을 동시에 고를 수 없고, 반드시 가로 방향 이웃 하나와 세로 방향 이웃 하나를 골라야 한다.)
• 드워프는 정확히 3개의 이웃과 동맹이 필요하다.
• 호빗은 매우 겁이 많아 네 이웃 모두와 동맹이 필요하다.

다시 말해, 인간을 제외한 각 마을은 정해진 개수의 동맹이 필요할 뿐, 어떤 이웃과 동맹을 맺는지는 상관하지 않는다. 인간에게만 동맹 상대가 마을의 반대편에 있으면 안 된다는 추가 제약이 있다.

이 조건들은 마을이 지도에서 어디에 위치하든 반드시 충족되어야 한다. 예를 들어 드워프 마을은 3개의 동맹을 원한다. 해안(가장자리)에 있다면 세 이웃 모두와 동맹을 맺어야 한다는 뜻이다. 섬의 모서리에 드워프 마을이 있다면 그 주민들은 결코 안전하다고 느낄 수 없다.

각 종족에 대해 가능한 동맹 배치는 아래 그림에 나와 있다(O는 마을 자신, X는 동맹 상대, .은 빈칸을 나타낸다):

 -elves---------------       -humans--------------       -dwarves-------------       -hobbits------------- |...   .X.   ...   ...|     |.X.   .X.   ...   ...|     |.X.   .X.   .X.   ...|     |.X.                  ||.OX   .O.   XO.   .O.|     |.OX   XO.   XO.   .OX|     |.OX   XOX   XO.   XOX|     |XOX                  ||...   ...   ...   .X.|     |...   ...   .X.   .X.|     |.X.   ...   .X.   .X.|     |.X.                  | ---------------------       ---------------------       ---------------------       --------------------- 

주어진 섬의 배치에 대해, 모든 주민이 안전하다고 느끼도록 동맹을 구성하는 것이 가능한지 판정하라.

첫째 줄에 섬의 크기를 나타내는 두 정수 R과 C가 주어진다. 이어지는 R개의 줄에 섬의 배치가 주어진다. 각 줄에는 0 이상 4 이하의 정수 C개가 공백으로 구분되어 주어진다:

• 0은 아무도 살지 않는 구역,
• 1은 엘프 마을,
• 2는 인간 마을,
• 3은 드워프 마을,
• 4는 호빗 마을을 의미한다.

(입력의 숫자는 항상 그 마을이 원하는 동맹의 개수와 같다.)

모든 주민이 안전하다고 느끼도록 동맹을 구성하는 것이 가능하면 첫 줄에 "Possible"을, 불가능하면 "Impossible!"을 출력하라(따옴표는 제외).

모든 테스트 케이스에서 1 ≤ R, C ≤ 70 이다.