Comparing Combinations


Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You really like combinatorics, especially with really big numbers! One day, you see a few queries on Stack Overflow.

Each query is in the following form: given four integers a_i, b_i, c_i, d_i, determine whether {a_i \choose {b_i}} < {c_i \choose {d_i}}.

Given your interest in the subject, you can't help but answer them!

Input Specification

The first line contains two integers: N and Q.

The next Q lines each contain four integers: a_i, b_i, c_i, and d_i.

Output Specification

Print Q lines.

For the i^{th} line, print YES if {a_i \choose {b_i}} < {c_i \choose {d_i}}, otherwise NO.

Constraints

For all subtasks, 1 \leq N, Q \leq 2 \times 10^5, 1 \leq b_i \leq a_i \leq N, 1 \leq d_i \leq c_i \leq N.

Subtask Points Additional Constraints
1 20 N \leq 20
2 20 N, Q \leq 5000
3 60 No additional constraints

Sample Input

200000 5
2 1 5 3
6 4 15 1
30 5 23 18
182935 35439 114354 69801
196004 98092 199416 97732

Sample Output

YES
NO
NO
NO
YES

Explaination for Sample Output

In the first query, {2 \choose 1} = 2 and {5 \choose 3} = 10. In this case, the left hand side is strictly less than the right hand side (2<10), so the answer is YES.

In the second query, {6 \choose 4} = 15 is not strictly less than {15 \choose 1} = 15, so the answer is NO.

In the third query, {142506 < 33649} is false.


Comments

There are no comments at the moment.