카드 뒤집기 게임

카드 뒤집기 게임은 혼자 하는 카드 게임으로, 두 종류의 카드 A, B를 사용한다. 카드 A에는 게임에 적용할 규칙이 적혀 있다. 구체적으로 그림 1과 같이 두 정수 $N$과 $M(\le N)$, 그리고 $N \times N$ 격자 형태로 문자 'O'와 'X'가 배치된 패턴 $P$가 적혀 있다.

그림 1

카드 B는 앞면에 문자 'O', 뒷면에 문자 'X'가 적힌 카드다. 카드 B 한 장은 카드 A에 적힌 패턴의 문자 하나를 나타내는 데 쓰이며, 이를 위해 충분히 많은 수의 카드 B가 준비되어 있다.

게임을 시작하자. 먼저 카드 A를 하나 고르고, 그 카드에 적힌 $N$ 값에 따라 $N \times N$ 격자 형태로 카드 B를 배치한다. 처음 배치하는 카드는 모두 'X'가 보이도록 놓아야 한다. 배치된 각 카드는 그림 2처럼 행과 열의 번호로 구분한다.

그림 2

카드의 초기 배치가 끝나면 플레이어는 아래에 설명하는 '뒤집기'를 필요에 따라 반복한다. 한 번의 '뒤집기'는 두 단계로 이루어진다.

• 단계 1: 카드가 놓인 $N \times N$ 격자에서 임의의 한 행 또는 한 열을 선택한다. 또한 카드 A에 적힌 정수 $M$에 따라 임의의 정수 $k(0 \le k < M)$를 선택한다.
• 단계 2: 단계 1에서 선택한 것이 행 $i$라면, $j \equiv k \pmod{M}$인 모든 $j$에 대해 격자 상에서 $(i,j)$ 위치에 있는 카드를 모두 뒤집는다. 마찬가지로 단계 1에서 선택한 것이 열 $j$라면, $i \equiv k \pmod{M}$인 모든 $i$에 대해 격자 상에서 $(i,j)$ 위치에 있는 카드를 모두 뒤집는다.

플레이어는 '뒤집기'를 반복해서 격자에 놓인 카드의 패턴과 카드 A에 그려진 패턴 $P$를 일치시켜야 한다. 이것이 실제로 가능한지 판별하자.

• $1 \le M \le N \le 1\,000$
• $P$에 속한 모든 문자는 'O' 또는 'X' 이다.