Flip Card Game

The Flip Card Game is a single-player card game that uses two types of cards: card A and card B.

Card A contains key game information. In particular, as shown in Figure 1, Card A displays two integers \(N\) and \(M\) (with \(M \leq N\)) and an \(N \times N\) pattern \(P\) consisting of the characters O and X in a matrix.

Card B has the character O on its front and X on its back. There are enough card B's so that each cell in the \(N \times N\) grid can be represented by one card B.

The game begins by choosing a card A and arranging the card B's into an \(N \times N\) grid. Initially, every card shows X. The cards are indexed by row and column, as shown in Figure 2.

After the initial arrangement, the player can perform the following flip operations repeatedly:

• Step 1: In the \(N \times N\) grid, choose any row or column and, based on the integer \(M\) from Card A, choose an arbitrary integer \(k\) such that \(0 \le k < M\).
• Step 2:
  • If a row \(i\) is chosen, then flip all cards in positions \((i, j)\) where \(j \equiv k \pmod{M}\).
  • If a column \(j\) is chosen, then flip all cards in positions \((i, j)\) where \(i \equiv k \pmod{M}\).

The goal is to perform a series of flip operations so that the resulting grid exactly matches the pattern \(P\) on Card A. Specifically, the character O is treated as 1 and X as 0. Each flip toggles the value (i.e. \(0 \leftrightarrow 1\)).

Formally, if we denote the binary state of a card at position \((i,j)\) by \(T(i,j)\) (with 0 representing X and 1 representing O), then starting from all 0's, flipping operations correspond to adding (modulo 2) values to certain positions. For a row flip at row \(i\) with choice \(k\), every cell \((i,j)\) with \(j \equiv k \pmod{M}\) is toggled; similarly, for a column flip. The final requirement is that for every cell \((i,j)\), \[ R(i,j) + C(i,j) \equiv P(i,j) \pmod{2}, \] where \(R(i,j)\) is the contribution from row flips (depending only on \(i\) and the residue of \(j\) modulo \(M\)) and \(C(i,j)\) is the corresponding contribution from column flips (depending on \(j\) and the residue of \(i\) modulo \(M\)). Through careful analysis, one can show that a necessary and sufficient condition for the existence of a sequence of moves is that for any two rows whose indices share the same residue modulo \(M\) and for any two columns whose indices share the same residue modulo \(M\), the parity differences in \(P\) must be consistent.

Your task is to decide whether it is possible to achieve the target pattern \(P\) by a sequence of valid flip operations.

inputFormat

The input consists of:

• A line containing two integers \(N\) and \(M\), where \(M \leq N\).
• Followed by \(N\) lines, each containing a string of length \(N\) composed solely of the characters O and X, representing the target pattern \(P\).

outputFormat

Output a single line containing true if it is possible to achieve the target pattern \(P\) by performing a sequence of flip operations starting from an all-X grid, and false otherwise.

sample

3 2
XXX
XXX
XXX

true