C

Rectangle XOR Game

Input: Standard Input

Output: Standard Output

 

There is a 01 matrix with n rows and m columns, having at least one 1. Rows are numbered 1 to n from top to bottom, columns are numbered 1 to m from left to right.

 

Two players move in turn. In each move, the player selects a rectangle (x1,y1)-(x2,y2) (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) and flips all the numbers (0→1, 1→0) in it (i.e. the flip all positions (x,y) where x1 ≤ x ≤ x2, y1 ≤ y ≤ y2)). The only restriction is that the top-left corner (i.e. (x1,y1)) must be changing from 1 to 0.

 

After a player's move, if the matrix contains only zeros, he wins.

 

Your task is to determine whether the first player can win, if both players play perfectly.

 

If he can win, count how many different first moves can lead to victory, and print the lexicographically smallest one (i.e. x1 should be as smallest as possible, then y1, x2, y2)

 

Input

The input contains at most 400 test cases. Each case begins with two integers n and m (1 ≤ n, m ≤ 100). The next n lines contain the matrix. Each line contains m integers (Either 0 or 1). There will be at least one 1 in the matrix.

 

The input ends with EOF

 

Output

For each test case, if the first player cannot win, print a single string "No" (without quotes), otherwise print five integers c x1 y1 x2 y2, where c is the number of winning first moves, and (x1,y1)-(x2,y2) is the lexicographically smallest first move.

 

Sample Input                                 Output for Sample Input

2 2

0 1

1 0

2 2

1 0

0 1

2 2

1 1

1 1

1 7

0 1 1 1 1 0 0

 

No

1 1 1 2 2

3 1 1 2 2

3 1 2 1 5

 

Problemsetter: Rujia Liu, Special Thanks: Md. Mahbubul Hasan, Yubin Wang

 

Explanation below:

 

 

 

 

Case 1:

 

2 2

0 1

1 0

 

The first player loses, because he has 4 moves, leading to:

 

0 0

1 0

 

0 0

1 1

 

0 1

0 0

 

0 1

0 1

 

The second player can flip all 1s to 0s.

 

Case 2:

 

2 2

1 0

0 1

 

This is winning, because the first player can flip the whole board and turn to the losing game analyzed above.

 

 

Case 3:

 

2 2

1 1

1 1

 

There are 3 winning moves, leading to the following games:

 

0 0

0 0

 

1 0

1 1

 

1 1

0 1

 

The lexicographically first one is (1,1)-(2,2)