Xortris

1990년, 당신은 오락실의 판도를 바꿀 비디오 게임 개발팀에서 일하고 있다. 플레이어에게는 흰 칸과 검은 칸으로 이루어진 직사각형 판이 주어진다. 목표는 판 전체를 흰색으로 만드는 것이다. 한 차례마다 플레이어는 무한히 공급되는 테트로미노 중 하나를 골라 조각 전체가 판 안에 들어가도록 옮기고 회전시킨 다음, 그 조각이 덮은 네 칸의 색을 모두 반대로 바꿀 수 있다. 테트로미노는 변끼리 맞닿아 하나로 이어진 정사각형 네 개를 말한다 (그림 1).

테스트 팀은 몇몇 단계가 아예 풀리지 않는다고 계속 항의한다. 테스터의 실력은 필요한 위치와 회전으로 조각을 놓기에 충분하니 원인은 다른 곳에 있다. 다음 디버깅 단계로, 주어진 단계를 풀 수 있는지 판정하는 프로그램을 작성하라.

그림 1: 모든 테트로미노. 출처: Wikimedia.

첫째 줄에 판의 크기를 나타내는 두 정수 $m$과 $n$이 주어진다 ($1 \le m, n \le 100$). 이어지는 $m$개의 줄에는 각각 $n$개의 문자가 주어진다. 문자 .은 흰 칸을, 문자 X는 검은 칸을 뜻한다.

단계를 풀 수 있으면 possible을, 풀 수 없으면 impossible을 한 줄에 출력한다.