Maximum Domino Placement on an n×n Grid with Diagonal Obstacles

You are given an n×n grid. On the main diagonal starting from the top‐left corner, k consecutive cells are blocked (obstacles). You are allowed to place several 1×2 dominoes on the grid. The dominoes must not overlap, and they must not cover an obstacle cell. You can place a domino either horizontally or vertically.

Your task is to output a placement scheme that uses as many dominoes as possible. It can be proven that, for example, when n = 4 and k = 2, at most 6 dominoes can be placed.

Note on grid indexing: In the output, the grid rows and columns are numbered from 1 to n. Each domino is represented by the coordinates of its two covered cells.

Input format (also shown below):
Two integers n and k (with 1 ≤ k ≤ n). The obstacles will be placed in cells (1,1), (2,2), …, (k,k).

Output format:
First, output an integer m representing the number of dominoes placed. Then output m lines, each containing four integers: r1 c1 r2 c2, denoting a domino covering cells (r1, c1) and (r2, c2).

inputFormat

The input consists of a single line containing two integers n and k, where:

• n: the size of the grid (n×n).
• k: the number of consecutive blocked cells along the main diagonal starting from the top-left corner.

Constraints: 1 ≤ k ≤ n. (n is such that a solution using bipartite matching is feasible.)

outputFormat

First, output a single integer m, the number of dominoes used in your placement. Then output m lines. Each line should contain four integers: r1, c1, r2, c2, representing that a domino covers the cells (r1, c1) and (r2, c2) on the grid. Cells are 1-indexed. The placement must obey the rules: dominoes do not overlap and do not cover any obstacle cells, and the number m should be as large as possible.

sample

4 2

6
1 3 1 2
2 4 2 3
3 1 3 2
3 3 3 4
4 2 4 1
4 4 4 3