Battle of the Iron Axes

In the game Battle of the Iron Axes, there is an \(H \times W\) board. The cell at row \(i\) and column \(j\) is denoted by \((i, j)\) (with \(i\) counted from the top and \(j\) counted from the left). There are \(N\) pieces placed on the board. When a player passes through cell \((R_i, C_i)\), they pick up the \(i\)th piece and gain a battle power of \(1\). Starting from cell \((1, 1)\) and moving only right or down at each step, the player must reach \((H, W)\).

The task is to compute the maximum battle power a player can obtain, and also to output a valid path that collects pieces in an order that yields this maximum battle power. Note that a piece can be collected only if the path goes through its cell. Since movements are restricted to only right and down, a cell \((R_i, C_i)\) can be visited after cell \((R_j, C_j)\) only if \(R_i \ge R_j\) and \(C_i \ge C_j\). Thus, you are essentially asked to choose a sequence of pieces from the provided \(N\) pieces such that for any two consecutive pieces \((R_j, C_j)\) and \((R_i, C_i)\) in the sequence, \(R_i \ge R_j\) and \(C_i \ge C_j\).

The output should include:

• The maximum battle power, i.e. the maximum number of pieces that can be collected along a valid path.
• A valid path from \((1,1)\) to \((H,W)\) that collects the pieces in the order chosen. The path is represented by listing all the cells (each cell represented by its row and column) visited along the way. Between any two consecutive cells in the path, the row value or the column value increases by exactly 1 (i.e. you move either right or down).

Note: If there are no pieces or none can be collected in a way that increases the battle power, the maximum battle power is \(0\) and the valid path is simply any valid path from \((1, 1)\) to \((H, W)\).

inputFormat

The first line of input contains three integers \(H\), \(W\), and \(N\) \( (1 \le H, W \le 10^5,\ 0 \le N \le 10^5)\). Each of the next \(N\) lines contains two integers \(R_i\) and \(C_i\) describing the row and column of the \(i\)th piece. It is guaranteed that \(1 \le R_i \le H\) and \(1 \le C_i \le W\).

outputFormat

On the first line, output the maximum battle power (i.e. the maximum number of pieces that can be collected). On the second line, output an integer \(L\) denoting the number of cells in the following path. Then output \(L\) lines, each containing two space‐separated integers representing the row and column of the cell in the order they are visited. The path must start at \((1, 1)\) and end at \((H, W)\), and every move between consecutive cells must be to the right or downward.

sample

3 3 2
2 2
3 2

2
5
1 1
1 2
2 2
3 2
3 3

</p>