Jaś and Małgosia have a rectangular chessboard with $K$ columns and $W$ rows ($W \le K$). Unfortunately, there are holes in some squares of this chessboard, and no pieces can be placed there. The reason for these holes is Jaś, who likes playing with a drill. Małgosia is not very happy about this, and since she is good at mathematics, she calculated the number of ways to place $W$ rooks on this chessboard (they can only be placed on squares without holes) such that they do not attack each other (i.e., no two rooks are in the same row or column). She wrote down the result and checks from time to time if it has changed.

Jaś, however, does not give up. He wants to drill as many additional holes as possible in such a way that Małgosia does not notice, i.e., the number of ways to place $W$ non-attacking rooks does not change. He asks you for help in determining the largest number of squares in which he could drill additional holes.

Task

Write a program that: reads the dimensions of the chessboard and the locations of the existing holes, finds the largest set of squares where holes can be drilled without changing the number of ways to place $W$ rooks on the chessboard, * indicates the appropriate squares.

Input

The first line contains three space-separated natural numbers $K, W, P$ ($1 \le W \le K$, $0 \le P \le K \cdot W \le 10^6$). The numbers $K$ and $W$ denote the number of columns and the number of rows, respectively. $P$ denotes the number of holes on the chessboard.

The next $P$ lines contain the description of the hole locations. Each line of the description contains two natural numbers $x, y$ separated by a single space ($1 \le x \le K, 1 \le y \le W$). This is the column number and row number at the intersection of which there is a hole. Each square appears in the description exactly once.

Output

The first line should contain exactly one integer $D$, equal to the maximum number of squares in which holes can be drilled.

In the next $D$ lines, print two integers each — the coordinates $x$ and $y$ of the squares (column number, row number) where holes can be drilled. The squares should be sorted lexicographically, first by the coordinate $x$, and in case of equal $x$ coordinates, by the coordinate $y$. If there are several possible sets of squares of the same size $D$, print any one of them.

Examples

Input 1

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

Output 1

2
1 2
2 1

Black circles represent the current placement of holes. White circles represent the squares where additional holes can be placed.