When \(n\) smallest non-negative integers (\(0,1,2,\ldots,n-1\)) are written, each operation works as follows.

• If you choose to delete even numbers, you will have \(\lfloor \frac{n}{2} \rfloor \) smallest non-negative integers remaining.
• If you choose to delete odd numbers, you will have \(\lfloor \frac{n+1}{2} \rfloor \) smallest non-negative integers remaining.

Let the former be operation \(0\) and the latter operation \(1\).

Furthermore, if \(k\) operations are performed, let \(x\) be the non-negative integer such that the \(k\)-th lowest bit corresponds to the \(k\)-th operation, and you will have \(\lfloor \frac{n+x}{2^k} \rfloor\) smallest non-negative integers remaining. We call this sequence of operations procedure \(x\).

With \(k\) operations, procedure \(x\) will delete all the non-negative integers \(l,l+1,\ldots,r\) if and only if \(\lfloor \frac{l+x}{2^k} \rfloor = \lfloor \frac{r+1+x}{2^k} \rfloor\). The set of \(x\) satisfying this condition can be represented as one or two intervals, considering the time when there is a carry from the \(k\)-th bit in \(l+x\) and \(r+1+x\). The problem gives \(N\) pairs of \(l\) and \(r\), and to examine the state where all the integers are deleted, you should compress the “coordinates” based on the carry and find the intersection of the intervals.

With the above in mind, consider the following dynamic programming.

• \(\mathrm{dp}_{k,i}\): whether you will win or lose if \(k\) operations are performed and the value \(x\) of the procedure is in the \(i\)-th interval after the coordinate compression.

If \(k \geq \lceil \log r_N \rceil\), at most one non-negative integer remains after the \(k\)-th operation, so we can use the above method and say you lose if nothing remains, and win otherwise. Let this be the initial state and go in descending order of \(k\). From the interval corresponding to \([l,r]\), we can check the intervals containing \([l,r]\) and \([l+2^k, r+2^k]\) after the \((k+1)\)-th operation (if not all the integers have been deleted) to determine which will win from the state \(k=0\). (The intervals \([l,r]\) and \([l+2^k, r+2^k]\) may not exist after \(k+1\) operations, but some intervals containing them do exist, because the coordinate compression is based on the time when there is a carry from the \((k+1)\)-th bit in each value).

The computational complexity should basically be \(\mathrm{O}(N \log N \log r_N)\), but \(\mathrm{O}(N \log r_N)\) can be achieved by finding the intervals after the coordinate compression in ascending order of \(k\) like radix sort, or updating \(\mathrm{dp}\) using two pointers, and so on.