题目背景

翻译自 CEOI2023 Day1 T2 Grading Server。

题目描述

竞赛委员会的主席注意到了一些可疑的网络活动 —— 有人想要攻击评测系统！

评测系统拥有特定的算力 $c_G$。黑客会尝试将 $c_G$ 降为 $0$（甚至更低）。系统被 $f_G$ 个防火墙保护着，每个防火墙都会将攻击的影响降低 $S$。

每个时刻，黑客可以进行以下两种操作之一：

• 击破一个防火墙，将 $f_G$ 降低 $1$（但不能低于 $0$），或者
• 用他所有的算力 $c_H$ 攻击系统，将 $c_G$ 降低 $\max(c_H - f_G\cdot S, 0)$。

但委员会主席可以反击：击破黑客的 $f_H$ 个防火墙之一；或者用系统的算力攻击黑客，类似地将 $c_H$ 降低 $\max(c_G - f_H \cdot S)$。委员会主席和黑客轮流行动，黑客先行动。

为了安排防御，委员会成员需要一个程序告诉他们，在 $Q$ 个不同的 $(c_H, f_H, c_G, f_G)$ 情况下，就算委员会主席采取了最优的行动，黑客是否依然能够击垮评测系统（将 $c_G$ 降低为 $0$ 或更低）。

输入格式

第一行两个整数 $S, Q$。

接下来 $Q$ 行，每行四个整数 $c_H, f_H, c_G, f_G$ 描述一个情况，分别为黑客的算力和防火墙数量，以及评测系统的算力和防火墙数量。

输出格式

你的程序应当输出 $Q$ 行，每行一个字符串 YES 或 NO。YES 表示无论委员会主席的行动如何，采取最优策略的黑客总能够让 $c_G$ 降为 $0$ 或更低；否则输出 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

提示

样例解释

考虑样例一的第一个情况：

• 首先，黑客攻击评测系统，将 $c_G$ 降低 $42 - 1\cdot 17 = 25$ 为 $8$；
• 接下来，委员会主席无法通过攻击降低 $c_H$，所以明智的选择是击破黑客的唯一的防火墙；
• 然而，黑客可以继续攻击评测系统，将 $c_G$ 降低 $25$ 为 $-17\leq 0$，击垮评测系统并毁掉第一天比赛日。

对于第二个情况：

• 一开始，黑客唯一能做的就是击破一个评测系统的防火墙；
• 接下来，委员会主席攻击黑客，将 $c_H$ 降低为 $26$；
• 接下来两轮，黑客同样只能攻击评测系统的防火墙。同时委员会主席每次攻击黑客，将 $c_H$ 降低为不大于 $0$ 的值，成功防御黑客的攻击。

数据范围与约定

• Subtask 1（5 分）：$S, c_H, c_G, f_H, f_G\leq 75$；
• Subtask 2（5 分）：$S, c_H, c_G, f_H, f_G\leq 300$；
• Subtask 3（10 分）：$S = 1$；
• Subtask 4（25 分）：$S, c_H, c_G, f_H, f_G\leq 2000$；
• Subtask 5（20 分）：$S\leq 400$；
• Subtask 6（20 分）：$f_H, f_G\leq 125$；
• Subtask 7（15 分）：无特殊限制。

对于所有数据，$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$。

限制

时间：4s
空间：1GB