Queen Game

Time limit1sMemory limit128 MB

Summary

Given N queens on an R by C board that move up, left, or up-left, decide if the first player wins with optimal play.

Level: Medium7 of 10
Topics: Game theory, Math, Bit manipulation
Solved: No attempts yet

Problem

Queen Game is a two-player game played on an $R \times C$ chessboard. Rows are numbered $1$ to $R$ from top to bottom, and columns $1$ to $C$ from left to right; the top-left cell is row $1$ , column $1$ .

$N$ queens are placed on the board. Several queens may occupy the same cell, and each cell can hold arbitrarily many queens.

The two players alternate turns. On your turn you choose one queen and move it in one of three directions:

up,
left, or
diagonally up-left.

You may move it by any number of cells, but a queen can never leave the board. When a queen reaches row $1$ , column $1$ , that queen is removed from the board. The player who removes the last queen wins.

Given the board size and the positions of the $N$ queens, and assuming both players play optimally, write a program that decides whether the first player has a winning strategy.

Input

The first line contains the number of test cases $T$ .

For each test case, the first line contains three integers $R$ , $C$ , and $N$ ( $1 \le R \le 25$ , $1 \le C \le 10^{15}$ , $1 \le N \le 1000$ ).

Each of the next $N$ lines contains the position of one queen: the row number and the column number, separated by a space.

Output

For each test case, print YES on its own line if the first player has a winning strategy, and NO otherwise.

Examples3

Example 1

Input

Expected output

NO
NO
YES

Example 2
Input
```
1
1 1 1
1 1
```
Expected output
```
NO
```
Example 3
Input
```
1
5 5 1
2 2
```
Expected output
```
YES
```