**Half Queen Cover solution codeforces** – You are given a board with 𝑛n rows and 𝑛n columns, numbered from 11 to 𝑛n. The intersection of the 𝑎a-th row and 𝑏b-th column is denoted by (𝑎,𝑏)(a,b).

## [Solution] Half Queen Cover solution codeforces

A half-queen attacks cells in the same row, same column, and on one diagonal. More formally, a half-queen on (𝑎,𝑏)(a,b) attacks the cell (𝑐,𝑑)(c,d) if 𝑎=𝑐a=c or 𝑏=𝑑b=d or 𝑎−𝑏=𝑐−𝑑a−b=c−d.

The first line contains a single integer 𝑛n (1≤𝑛≤1051≤n≤105) — the size of the board.

## [Solution] Half Queen Cover solution codeforces

In the first line print a single integer 𝑘k — the minimum number of half-queens.

In each of the next 𝑘k lines print two integers 𝑎𝑖ai, 𝑏𝑖bi (1≤𝑎𝑖,𝑏𝑖≤𝑛1≤ai,bi≤n) — the position of the 𝑖i-th half-queen.

If there are multiple solutions, print any.

1

1 1 1

2

## [Solution] Half Queen Cover solution codeforces

1 1 1

3

2 1 1 1 2

## Half Queen Cover solution codeforces

Example 11: one half-queen is enough. Note: a half-queen on (1,1)(1,1) attacks (1,1)(1,1).

Example 22: one half-queen is enough too. (1,2)(1,2) or (2,1)(2,1) would be wrong solutions, because a half-queen on (1,2)(1,2) does not attack the cell (2,1)(2,1) and vice versa. (2,2)(2,2) is also a valid solution.

Example 33: it is impossible to cover the board with one half queen. There are multiple solutions for 22 half-queens; you can print any of them.