Umka and a Long Flight
Contest: Codeforces Round 863 (Div. 3)
Difficulty rating: 1600
Tags: constructive algorithms, implementation, math

The girl Umka loves to travel and participate in math olympiads. One day she was flying by plane to the next olympiad and out of boredom explored a huge checkered sheet of paper.

Denote the $$$n$$$-th Fibonacci number as $$$F_n = \begin{cases} 1, & n = 0; \\ 1, & n = 1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{cases}$$$

A checkered rectangle with a height of $$$F_n$$$ and a width of $$$F_{n+1}$$$ is called a Fibonacci rectangle of order $$$n$$$.

Umka has a Fibonacci rectangle of order $$$n$$$. Someone colored a cell in it at the intersection of the row $$$x$$$ and the column $$$y$$$.

It is necessary to cut this rectangle exactly into $$$n+1$$$ squares in such way that

- the painted cell was in a square with a side of $$$1$$$;
- there was at most one pair of squares with equal sides;
- the side of each square was equal to a Fibonacci number.

Will Umka be able to cut this rectangle in that way?

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — number of test cases.

For each test case the integers $$$n$$$, $$$x$$$, $$$y$$$ are given ($$$1 \le n \le 44$$$, $$$1 \le x \le F_n$$$, $$$1 \le y \le F_{n+1}$$$) — the order of the Fibonacci rectangle and the coordinates of the colored cell.

Output format:
For each test case, print "YES" if the answer is positive, and "NO" otherwise.

You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive answer).

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

Note:
The first, third and fourth test cases.

Example input:
12
1 1 1
2 1 2
3 1 4
3 3 2
4 4 6
4 3 3
5 6 5
5 4 12
5 2 12
4 2 1
1 1 2
44 758465880 1277583853

Example output:
YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO

Editorial:
1. $$$F_0^2 + F_1^2 +\ldots + F_n^2 = F_n\cdot F_{n+1}$$$, which can be proved by induction: $$$F_n\cdot F_{n+1} = F_n\cdot (F_{n-1}+F_n) = F_{n-1} \cdot F_n + F_n^2$$$.
2. If the partition exists, it has the form $$$[F_0, F_1, \ldots, F_n]$$$, since the area of the rectangle with another partition will be greater than $$$F_n \cdot F_{n+1}$$$.
3. We will cut the rectangles in the order $$$F_n, F_{n-1}, \ldots, F_0$$$. Denote the coordinates of the colored cell at the step $$$n$$$ as $$$\langle x_n, y_n\rangle$$$.
4. If $$$F_{n-1} <y_n\le F_n$$$ and $$$n> 1$$$, then there is no partition, since the square $$$F_n$$$ at any location overlaps the colored cell.
5. Cut off the square $$$F_n$$$ from the right or left edge, depending on the location of the colored cell, that is, $$$\langle x_{n-1}, y_{n-1} \rangle = \langle y_n, x_n\rangle$$$ or $$$\langle x_{n-1}, y_{n-1} \rangle = \langle y_n - F_n, x_n \rangle$$$.
6. Suppose that it was advantageous to cut it not from the edge, then it is necessary to cut the rectangles $$$z\times F_n$$$ and $$$(F_{n-1}-z)\times F_n$$$, where $$$1\le z <F_{n+1}-F_n =F_{n-1}$$$ using the set $$$[F_0, F_1 \ldots F_{n-1}]$$$. Then $$$F_{n-1}$$$ will not enter the partition, but $$$2\cdot F_{n-2}^2 < (2F_{n-2}+F_{n-3})^2 + 1 = ( F_{n-2} + F_{n-1})^2 +1$$$, so $$$F_1^2 + F_2^2 + \ldots +2 \cdot F_{n-2}^2 < F_0^2 +F_1^2 +\ldots+F_{n-1}^2 = F_{n-1} \cdot F_n = z \cdot F_n + (F_{n-1} - z) \cdot F_n$$$. We came to a contradiction.