Card Flipping Game is a solitaire card game that uses two types of cards, A and B. Card A contains information about the rules to be applied in the game. Specifically, as shown in Figure 1, it contains two integers $N$ and $M$ ($M \le N$), and a pattern $P$ where the characters 'O' and 'X' are arranged in an $N \times N$ grid.

Figure 1

Card B is a card with the character 'O' on the front and 'X' on the back. One card B will be used to represent one character of the pattern on card A, and a sufficient number of cards B are prepared for this purpose.

Let's start the game. First, select one card A, and according to the value of $N$ written on it, arrange cards B in an $N \times N$ grid. The initially placed cards must all be placed such that 'X' is visible. Each placed card is identified by its row and column number, as shown in Figure 2.

Figure 2

Once the initial arrangement of cards is complete, the player repeats the 'flip' operation described below as needed. One 'flip' consists of two steps:

• Step 1: Select an arbitrary row or column in the $N \times N$ grid where the cards are placed. Also, select an arbitrary integer $k$ ($0 \le k < M$) according to the integer $M$ written on card A.
• Step 2: If the selection in Step 1 was row $i$, flip all cards at position $(i, j)$ on the grid for all $j$ such that $j \equiv k \pmod M$. Similarly, if the selection in Step 1 was column $j$, flip all cards at position $(i, j)$ on the grid for all $i$ such that $i \equiv k \pmod M$.

The player must repeat the 'flip' operation to make the pattern of cards on the grid match the pattern $P$ drawn on card A. Determine if this is actually possible.

Implementation Details

You must implement the following function:

bool reversal(int N, int M, vector<string> P)

• This function is called exactly once.
• The integer $N$ given as an argument represents the size of the grid.
• The integer $M$ given as an argument represents the interval of cards flipped in a 'flip'.
• The array $P$ given as an argument is an array consisting of $N$ strings of length $N$, where $P[i]$ represents the $i$-th row of the pattern to be created.
• This function should return true if the pattern $P$ can be created by applying 'flips' from the initial arrangement of cards on the grid, and false otherwise.

You must not execute any input/output functions in any part of the submitted source code.

Constraints

• $1 \le M \le N \le 1000$
• All characters in $P$ are 'O' or 'X'.

Subtasks

1. (11 points)
   • $N \times M \le 10$
2. (50 points)
   • $M = 1$
3. (39 points)
   • No additional constraints.

Interaction

The sample grader receives input in the following format:

• Line 1: $N \ M$
• Line $2+i$: $P[i]$ (for $0 \le i < N$)

Note that the sample grader may differ from the grader used in actual evaluation.

Examples

Input 1

5 2
XXXOX
XXXOX
OOOXO
XOXXX
XOXXX

Output 1

true

Note

The figure below shows the process of how the card pattern changes according to the selected row/column number and the value of $k$, starting from the initial state. Through this process, you can see that the pattern $P$ is finally created.