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 (3 ≤ n, m ≤ 100, 1 ≤ x, 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
y2 then it is present at cells (
y1) and (
You can fill the board by placing each domino either vertically or horizontally.
If there are multiple solutions, you can output any of them.
3 4 1 3
YES 4 2 1 3 1 2 2 2 3 1 2 1 3 1 4 2 4
3 3 2 2