A newly discovered organism can be represented as a set of cells on an infinite grid. There is a coordinate system on the grid such that each cell has two integer coordinates \(x\) and \(y\). A cell with coordinates \(x=a\) and \(y=b\) will be denoted as \((a, b)\).
Initially, the organism consists of a single cell \((0, 0)\). Then zero or more divisions can happen. In one division, a cell \((a, b)\) is removed and replaced by two cells \((a+1, b)\) and \((a, b+1)\).
For example, after the first division, the organism always consists of two cells \((1, 0)\) and \((0, 1)\), and after the second division, it is either the three cells \((2, 0)\), \((1, 1)\) and \((0, 1)\), or the three cells \((1, 0)\), \((1, 1)\) and \((0, 2)\).
A division of a cell \((a, b)\) can only happen if the cells \((a+1, b)\) and \((a, b+1)\) are not yet part of the organism. For example, the cell \((1, 0)\) cannot divide if the organism currently consists of the three cells \((1, 0)\), \((1, 1)\) and \((0, 2)\), since the cell \((1, 1)\) that would be one of the results of this division is already part of the organism.
You are given a set of forbidden cells \({(c_i, d_i)}\). Is it possible for the organism to contain none of those cells after zero or more divisions?
Note
In the first test case, dividing the following cells in the following order creates an organism without any forbidden cells: \((0, 0)\), \((1, 0)\), \((1, 1)\), \((0, 1)\), \((2, 1)\), \((2, 2)\), \((1, 2)\), \((1, 1)\). The following picture demonstrates how the organism changes during this process:
In the second test case, you can see that, surprisingly, any organism always has at least one cell in the \(0 \le x, y \le 3\) square, no matter how many divisions we do.