Problem Assignment BM33PAL

Parity Sensitive Matrix Elements

In this problem, we consider integer rectangular matrices consisting of M×N cells. The indices of the rows and the columns are 0,1,2, ..., M−1 and 0,1,2, ..., N−1, respectively.
The parity of an integer value x is the reminder of integer division x / 2, that is, the parity of x is 1 when x is odd and the parity of x is 0 when x is even.
A cell C with with coordinates [r][c] is said to be parity sensitive if at least one of the four following conditions is satisfied:

1. There are at least two cells in row r to the right of C. The parity of all values in row r to the right of C is the same.
2. There are at least two cells in row r to the left of C. The parity of all values in row r to the left of C is the same.
3. There are at least two cells in column c above C. The parity of all values in column c above C is the same.
4. There are at least two cells in column c below C. The parity of all values in column c below C is the same.

A parity sensitive representation of matrix A is another matrix B of the same size as matrix A. The entries in the matrix B are defined as follows:

B[r][c] = 'X' if A[r][c] is parity sensitive.
B[r][c] = '.' if A[r][c] is not parity sensitive.

Image 1. A matrix and its parity sensitive representation. Image corresponds to Example 1 below.

The task

Print parity sensitive representation of an input matrix.

Input

The first input line contains two integers M and N representing the number of rows and the number of columns of the input matrix.
Next, there are exactly M lines. Each line contains N values, the values correspond to the values in a particular row in the matrix. All values are separated by single space.
It holds 2 ≤ M, N ≤ 1000, all values in the matrix are positive integers less than 100.

Output

The output contains M lines representing the parity sensitive representation of the input matrix. Consecutive values in one line are separated by single space.

Example 1

Input

6 7
2 3 4 5 5 5 1
2 2 2 1 1 1 1
3 1 3 1 3 1 4
5 2 2 2 3 3 3
2 6 1 1 3 2 2
5 5 5 2 2 2 1

Output

. . X X X . .
. . X X X . . 
X . X X X X X 
. . X X X X . 
. . X . X X . 
. . X X X . .

Example 2

Input

8 8
2 3 4 8 7 9 7 1
3 1 5 6 2 4 1 9
1 9 1 1 6 2 2 1
2 3 7 6 5 3 8 2
8 8 5 7 6 1 3 7
8 9 2 8 5 5 3 7
4 4 6 1 9 7 9 7
3 8 9 4 6 4 4 6

Output

. . . X X X . . 
. . X X . X . .
. X X X X . X X 
. X . . . X . X 
. X X . X X . . 
. X . X X X . . 
. . X X X X . . 
. . X X X X . .

Example 3

Input

10 10
9 1 3 2 6 3 6 7 1 5
5 4 1 4 2 3 1 6 8 9
7 4 6 3 6 3 5 8 8 1
8 9 2 7 4 9 3 6 7 2
2 1 5 9 4 4 2 1 3 4
5 7 5 8 9 6 4 7 2 5
2 2 8 6 3 3 2 3 1 7
4 8 2 5 1 7 3 6 2 5
3 7 9 8 1 5 7 5 9 6
9 4 2 6 7 2 1 5 8 5

Output

. . X X . . X X . .
. . . . . . . . . . 
X . X X X X . . . X
X . . . X X . . . X 
. . . . X X . . . . 
. . X X X . . . . . 
. . X X X . X X . . 
X . X X X . X X . . 
. . X X . . . . . . 
. . . . . . . . . .

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set