Cut Board

Cut Board

A rectangular board of size n * m has 1 * 1 cells. x consecutive cells from the first row starting from the top-left and y consecutive cells from the last row starting from the bottom-right are cut off. Can you fill all the cells of the remaining board using some 2 * 1 dominoes such that none overlap or hang off the edge?


Write the program which takes in four integers n, m, x and y and prints whether the remaining board can be filled with dominoes, and if yes, prints one way to place the dominoes.


Consists of a single line containing four space-separated integers n, m, x and y (3n, m100, 1x, y < m).


Print NO in a single line if you cannot fill all the cells of the cut board using dominoes.

Otherwise, print YES in the first line, and a single integer in the second line denoting the number of dominoes required.

In the next lines, print four space-separated integers denoting the location of the domino. The x-coordinate corresponds to the row number and the y-coordinate corresponds to the column number.

If the location of domino is x1, y1, x2, y2 then it is present at cells (x1, y1) and (x2, y2).

You can fill the board by placing each domino either vertically or horizontally.

If there are multiple solutions, you can output any of them.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 4 1 3
Output example #1
2 1 3 1
2 2 2 3
1 2 1 3
1 4 2 4
Input example #2
3 3 2 2
Output example #2