P9730 [CEOI 2023] Grading Server

Translated from CEOI 2023 Day 1 T2 [Grading Server](https://www.ceoi2023.de/wp-content/uploads/2023/09/2-grading-server.pdf).

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.

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.

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`.

#### 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