Background

Translated from CEOI 2023 Day 1 T2 Grading Server.

Problem Description

The president of the contest committee has noticed some suspicious network activity—someone is trying to attack the grading system!

The grading system has a certain computing power $c_G$. The hacker will try to reduce $c_G$ to $0$ (or even lower). The system is protected by $f_G$ firewalls, and each firewall reduces the effect of an attack by $S$.

At each moment, the hacker can perform one of the following two actions:

• Break one firewall, decreasing $f_G$ by $1$ (but not below $0$), or
• Attack the system with all his computing power $c_H$, decreasing $c_G$ by $\max(c_H - f_G\cdot S, 0)$.

But the committee president can fight back: break one of the hacker’s $f_H$ firewalls; or attack the hacker using the system’s computing power, similarly decreasing $c_H$ by $\max(c_G - f_H \cdot S,0)$. The committee president and the hacker take turns, and the hacker moves first.

To plan the defense, the committee members need a program that tells them, for $Q$ different cases $(c_H, f_H, c_G, f_G)$, whether the hacker can still take down the grading system (reduce $c_G$ to $0$ or below) even if the committee president plays optimally.

Input Format

The first line contains two integers $S, Q$.

The next $Q$ lines each contain four integers $c_H, f_H, c_G, f_G$ describing one case: the hacker’s computing power and number of firewalls, and the grading system’s computing power and number of firewalls.

Output Format

Your program should output $Q$ lines, each containing a string YES or NO. Output YES if, no matter what the committee president does, a hacker who plays optimally can always reduce $c_G$ to $0$ or below; otherwise output NO.

17 2
42 1 33 1
42 1 33 7

YES
NO

1 1
999999999999 999999999999 999999999999 999999999999

YES

2 1
1000000000000 0 1 1000000000000

NO

Hint

Sample Explanation

Consider the first case in the sample:

• First, the hacker attacks the grading system, decreasing $c_G$ by $42 - 1\cdot 17 = 25$ to $8$;
• Next, the committee president cannot reduce $c_H$ by attacking, so the wise choice is to break the hacker’s only firewall;
• However, the hacker can keep attacking the grading system, decreasing $c_G$ by $25$ to $-17\leq 0$, taking down the grading system and ruining Day 1 of the contest.

For the second case:

• At the start, the only thing the hacker can do is to break one firewall of the grading system;
• Next, the committee president attacks the hacker, decreasing $c_H$ to $26$;
• In the next two rounds, the hacker can again only attack the grading system’s firewalls. Meanwhile, each time the committee president attacks the hacker, decreasing $c_H$ to a value not greater than $0$, successfully defending against the hacker’s attack.

Constraints and Notes

• Subtask 1 (5 points): $S, c_H, c_G, f_H, f_G\leq 75$;
• Subtask 2 (5 points): $S, c_H, c_G, f_H, f_G\leq 300$;
• Subtask 3 (10 points): $S = 1$;
• Subtask 4 (25 points): $S, c_H, c_G, f_H, f_G\leq 2000$;
• Subtask 5 (20 points): $S\leq 400$;
• Subtask 6 (20 points): $f_H, f_G\leq 125$;
• Subtask 7 (15 points): No additional constraints.

For all testdata, $1\leq S\leq 3\times 10 ^ 4$, $1\leq c_H, c_G\leq 10 ^ {12}$, $0\leq f_H, f_G\leq 10 ^ {12}$, $1\leq Q\leq 2.5\times 10 ^ 5$.

Limits

Time: 4s.
Memory: 1GB.

Translated by ChatGPT 5