Problem E
Illumination

Consider a square grid with lamps in fixed locations. Each lamp can either illuminate its row or its column, but not both. The illumination of each lamp extends over a limited distance.

Any square in the grid should only be illuminated by at most one lamp in its row and by at most one lamp in its column (one of each is acceptable, as is just the row, just the column, or neither). Determine if it is possible for all lamps to be lit while satisfying these constraints.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains three positive integers, $n$, $r$ and $k$ ($1 \le n, r, k \le 1\, 000, k \le n^2$), where $n$ is the size of one side of the square grid, $r$ is the maximum reach of a lamp, and $k$ is the number of lamps. The next $k$ lines will each contain two positive integers $i$ and $j$ ($1 \le i, j \le n$), indicating that there is a lamp in the grid at row $i$, column $j$.

Each lamp can illuminate squares at most $r$ units away, and can also illuminate its own square, so the maximum number of squares it can illuminate is $2 r + 1$. All lamps will be in distinct locations.

Output

Output a single integer, $1$ if it is possible to light all of the lamps and $0$ if it is not possible.

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

1

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

0