Problem Description

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

The grading system has a specific computational power \( c_G \). Hackers attempt to reduce \( c_G \) to 0 (or even lower). The system is protected by \( f_G \) firewalls, each reducing the impact of the attack by \( S \).

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

• Break through one firewall, reducing \( f_G \) by 1 (but not below 0), or
• Use all their computational power \( c_H \) to attack the system, reducing \( c_G \) by \( \max(c_H - f_G \cdot S, 0) \).

However, the chairman can counter-attack: break through one of the hacker's \( f_H \) firewalls, or use the system's computational power to attack the hacker, similarly reducing \( c_H \) by \( \max(c_G - f_H \cdot S) \). The chairman and the hacker take turns, with the hacker acting first.

To plan the defense, the committee members need a program to tell them, for \( Q \) different scenarios of \( (c_H, f_H, c_G, f_G) \), whether the hacker can still defeat the grading system (reduce \( c_G \) to 0 or lower) even if the chairman takes the optimal actions.

Input Format

The first line contains two integers \( S \) and \( Q \).

The next \( Q \) lines each contain four integers \( c_H, f_H, c_G, f_G \), describing a scenario, representing the hacker's computational power and number of firewalls, and the grading system's computational power and number of firewalls.

Output Format

Your program should output \( Q \) lines, each containing a string YES or NO. YES indicates that the hacker can always reduce \( c_G \) to 0 or lower with the optimal strategy, regardless of the chairman's actions; otherwise, output NO.

Sample Input and Output

Sample Input #1

17 2
42 1 33 1
42 1 33 7

Sample Output #1

YES
NO

Sample Input #2

1 1
999999999999 999999999999 999999999999 999999999999

Sample Output #2

YES

Sample Input #3

2 1
1000000000000 0 1 1000000000000

Sample Output #3

NO

Notes/Hints

Sample Explanation

Consider the first scenario of Sample Input #1:

• Initially, the hacker attacks the grading system, reducing \( c_G \) by \( 42 - 1 \cdot 17 = 25 \) to 8;
• Next, the chairman cannot reduce \( c_H \) by attacking, so the wise choice is to break through the hacker's only firewall;
• However, the hacker can continue to attack the grading system, reducing \( c_G \) by 25 to -17 ≤ 0, defeating the grading system and ruining the first competition day.

For the second scenario:

• Initially, the hacker can only break through one of the grading system's firewalls;
• Next, the chairman attacks the hacker, reducing \( c_H \) to 26;
• In the next two rounds, the hacker can only attack the grading system's firewalls. Meanwhile, the chairman attacks the hacker each time, reducing \( c_H \) to a value not greater than 0, successfully defending against the hacker's attack.

Data Range and Constraints

• 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 special restrictions.

For all data, \( 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 \).

Constraints

Time: 4s
Space: 1GB

见题面 Input 部分

见题面 Output 部分