Zeroing Boards Game

There are \(k\) boards. Each board is an \(n\times m\) grid. Initially, exactly three cells in each board are set to \(0\) and all other cells are \(1\). Two players, A and B, take turns. In each turn a player must choose one board and then choose one of the following moves on that board:

• Select a row and set all cells in that row to \(0\).
• Select a column and set all cells in that column to \(0\).
• Select a row and a column and set all cells in the chosen row and column to \(0\).

The move is allowed only if at least one cell changes its value from \(1\) to \(0\) as a result of the move. If a player cannot make a valid move on his turn, he loses. Determine whether the first player has a winning strategy when both players play optimally.

This is an impartial game which can be analyzed by finding the Grundy number (or nimber) for each board. For a board, we define its state as \((r,c)\), where \(r\) is the number of rows that are not completely zero and \(c\) is the number of columns that are not completely zero. A move corresponds to reducing \(r\) (by a row removal), \(c\) (by a column removal), or both \(r\) and \(c\) (by a combined removal). The Grundy number \(G(r,c)\) is given by the recursion:

[ G(r,c)=\mathtt{mex}{G(r-1,c),;G(r,c-1),;G(r-1,c-1)} ]

The overall game is equivalent to the disjunctive sum of the boards, and the first player wins if and only if the XOR of the Grundy numbers of all boards is nonzero.

inputFormat

Input Format:

The first line contains three integers \(k, n, m\) where \(k\) is the number of boards and \(n\) and \(m\) are the dimensions of each board. For each board, the next three lines each contain two integers \(r\) and \(c\) \((1\le r\le n,\;1\le c\le m)\) indicating that the cell at row \(r\) and column \(c\) is initially \(0\). It is guaranteed that each board has exactly three \(0\)s and the remaining cells are \(1\).

outputFormat

Output Format:

Output a single line containing Yes if the first player can force a win, or No otherwise.

sample

2 3 3
1 1
1 2
1 3
1 1
2 1
3 1

No