Conveyor
Contest: Codeforces Round 821 (Div. 2)
Difficulty rating: 2700
Tags: constructive algorithms, dp, math

There is a conveyor with $$$120$$$ rows and $$$120$$$ columns. Each row and column is numbered from $$$0$$$ to $$$119$$$, and the cell in $$$i$$$-th row and $$$j$$$-th column is denoted as $$$(i, j)$$$. The top leftmost cell is $$$(0, 0)$$$. Each cell has a belt, and all belts are initially facing to the right.

Initially, a slime ball is on the belt of $$$(0, 0)$$$, and other belts are empty. Every second, the state of the conveyor changes as follows:

- All slime balls on the conveyor move one cell in the direction of the belt at the same time. If there is no cell in the moved position, the slime gets out of the conveyor, and if two slime balls move to the same cell, they merge into one.
- All belts with slime ball in the previous second change direction at the same time: belts facing to the right become facing to the down, and vice versa.
- A new slime ball is placed on cell $$$(0, 0)$$$.

There are $$$q$$$ queries, each being three integers $$$t$$$, $$$x$$$, and $$$y$$$. You have to find out if there is a slime at the cell $$$(x, y)$$$ after $$$t$$$ seconds from the start. Can you do it?

Input format:
The first line contains one integer $$$q$$$ ($$$1 \le q \le 10^4$$$) — the number of queries.

The only line of each query contains three integers $$$t$$$, $$$x$$$, and $$$y$$$ ($$$0 \le t \le 10^{18}$$$, $$$0 \le x, y < 120$$$).

Output format:
Print the answer for each test case, one per line. If there is a slime ball in the cell $$$(x, y)$$$ after $$$t$$$ seconds from the initial state, print "YES". Otherwise, print "NO".

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The state of conveyor with $$$t = 0$$$. Red arrow represents the direction of each belt, and blue figure represents slime.

The state of conveyor with $$$t = 1$$$.

The state of conveyor with $$$t = 2$$$.

Example input:
6
1 1 0
5 1 3
0 0 0
2 4 5
2 0 2
1547748756 100 111

Example output:
NO
YES
YES
NO
YES
YES

Editorial:
In the conveyor, cells with same $$$(i + j)$$$ value consists a diagonal ($$$i$$$ is row number, $$$j$$$ is column number). Let's call them $$$(i + j)$$$-th diagonal. So there are $$$239$$$ diagonals, from $$$0$$$th to $$$238$$$th.
Now, we can find every slime ball move to the next diagonal for every second. It means no two slime ball merge forever.
Given $$$t$$$, $$$x$$$, $$$y$$$, cell $$$(x, y)$$$ belongs to $$$(x + y)$$$-th diagonal. If $$$t < x + y$$$, the answer is NO because there is no slime ball in $$$(x + y)$$$-th diagonal yet. If $$$t \ge x + y$$$, $$$(x + y)$$$-th diagonal contains one slime ball, and the ball is placed on cell $$$(0, 0)$$$ after $$$(t - x - y)$$$ seconds from the start. So $$$(t - x - y)$$$ slime balls passed this diagonal before.
Now, find out which cell contains clime ball among the diagonal. To do this, we use following method: simulate with $$$(t - x - y)$$$ slime balls to check how many slime reach each cell of the diagonal, and repeat this with $$$(t - x - y + 1)$$$ slime balls. Exactly one cell will show different result, and this cell is where $$$(t - x - y + 1)$$$-th slime ball passes through. If this cell is equal to $$$(x, y)$$$, the answer is YES. Otherwise the answer is NO.
Simulation with $$$x$$$ slime balls processes as follows:
• Place $$$x$$$ slime balls on cell $$$(0, 0)$$$.
• move slime balls to next diagonal. For each cell, if the cell contains $$$k$$$ slime balls, $$$\lceil \frac{k}{2} \rceil$$$ moves to right and $$$\lfloor \frac{k}{2} \rfloor$$$ moves to down.
• Repeat the second step. If slime balls reached aimed diagonal, stop and find the result.