读前提示：本篇题解较长，并且请注意先手满足的结论如果让后手满足要难得多。

网上那篇题解问题有点多。

记 $n=\max{c_H,f_H,c_G,f_G}$。

我们发现每一次有盾不太好处理，于是先将 $c_H$ 减去 $f_G\times S$，然后每一次能够选择加上 $S$，最多加 $f_G$ 次（记 $f_G=f_1$ 称为次数，初值为 $c_H=A_1$ 称为攻击力），$c_G$ 同理，有 $f_2,A_2$。

记攻破防火墙为防守，攻击系统为进攻。

这个博弈的结束条件是次数为 $0$ 并且攻击力 $\leq 0$（注意中间过程中攻击力可能 $<0$ ）。

这个博弈对于双方是公平的，在 dp 时可以直接通过替换先后手来避免额外记录 0/1。

我们记一个状态/局面为 $(A_1,f_1,A_2,f_2)$，也用这个符号表示先手必胜或必败，胜记为 $1$。

这个博弈每一维都有单调性，即 $(A_1+1,f_1,A_2,f_2)\geq (A_1,f_1,A_2,f_2)$，其余维同理。

我们记一个局面为有用的，当且仅当通过现在的分析，这个局面还没有确定最优的下一步并且没有确定这个局面的输赢。

Subtask 3

显然的结论：

• 在 $A_1\leq 0$ 时必然选择防守。（*1）

• 如果 $A_1\geq S\geq A_2$，那么先手每次选择攻击，后手攻击力只会越来越少，最终死亡。（*2）

• 如果 $A_2\geq S$，先手必然选择进攻，否则在对手进攻后会使 $A_1,f_1$ 都减小进入更劣局面。（*3）

• 如果 $A_1\geq 0\geq A_2$，先手可以通过攻击进入情况 $A_1\geq S\geq A_2$。（*4）

在如上结论下，我们知道有用局面满足 $0\leq A_1,A_2< S$。

对于这个 Subtask，模拟如上过程即可，唯一的复杂度贡献是在 $A_1,A_2\geq S$ 时的 $\log V$（复杂度证明就是每过两轮 $A_2$ 会减半）。

时间复杂度 $\mathcal{O}(q\log V)$。

Subtask 124

对于有用局面 $(A_1,f_1,A_2,f_2)$ 的限制除了 $A_1,A_2\in[0,S)$，还有什么？

我们会将 $A_1,A_2$ 不断加 $S$，最后他们都会大于 $0$，考虑初始输入的 $A'_1,A'_2$，有：

$$A'_*-A_*=f_*\times S$$

因此 $f_*\leq \dfrac{n}S$。

至此状态数被减少到了 $n^2$ 个，DP 预处理他们，询问在两个都 $\geq S$ 时仍然暴力跑，时间复杂度 $\mathcal{O}(n^2+q\log V)$。

Subtask 5

我们通过刚刚的尝试，发现通过分析简化有用局面是一种有效的优化方式，这启发我们继续分析。

对于有用局面 $(A_1,f_1,A_2,f_2)$，先手有一种很暴力的策略，每次都选择防守，而根据（*3），对手只能进攻。

记 $\Delta_1=S-A_2,\Delta_2=S-A_1$，也就是 $(A_1,f_1,A_2,f_2)\to(A_1+\Delta_1,f_1-1,A_2,f_2)$，

将这个过程做 $f_1$ 次，如果攻击力已经比 $S$ 大，先手直接获胜。

这样的话，有用局面又多了一个限制：$A_1+\Delta_1\times f_1\leq S$。

同时如果先手选择进攻，后手也可以不断防守，有限制：$A_2-A_1+\Delta_2\times f_2\leq S$。

做一些放缩，最终有：

$$\Delta_1\times f_1\leq S-A_1=\Delta_2,\Delta_2\times f_2\leq 2S$$

这样的状态总共有 $S^2\ln S$ 种，DP 之，可以做到 $\mathcal{O}(S^2\ln S+q\log V)$。

Subtask 6（与正解无关）

但是与 remark 做法有关。

还能再给力一点吗？

神奇的结论：$\forall (f_1,f_2),\exist \gamma(f_1,f_2)$ 满足 $A_2\geq \gamma(f_1,f_2)$ 就使用进攻，否则使用防守。

首先我们想，这个结论成立必须满足我们对于同一个 $A_2$ 肯定使用同一个策略。

仔细想想，这其实是显然的，因为对于同一个 $f_1,f_2,A_2$ 用进攻/防守能赢 $A_1$ 的一定是一个后缀，选择较大的那个后缀就好了。

这样的话，记 $\forall f_1,f_2$ 记 $h_A(A_2)$ 为使用进攻最小满足 $(A_1,f_1,A_2,f_2)=1$ 的 $A_1$，$h_F(A_2)$ 为使用防守最小满足 $(A_1,f_1,A_2,f_2)=1$ 的 $A_2$，只要证明 $\delta(A_2)=h_F(A_2)-h_A(A_2)$ 单调递减就可以了。

然后注意到如下事实：

• 如果使用攻击，则 $(A_1,f_1,A_2,f_2)\leq (A_1+1,f_1,A_2+1,f_2)$，证明可以考虑模拟一轮操作。
• 如果使用防守，则 $(A_1,f_1,A_2,f_2)\geq (A_1+1,f_1,A_2+1,f_2)$，证明也可以考虑模拟一轮操作。

那么有：

$$h_A(A_2+1)\leq h_A(A_2)+1$$ $$h_F(A_2+1)\geq h_F(A_2)+1$$

两式相减，有：

$$h_A(A_2+1)-h_F(A_2+1)\leq h_A(A_2)-h_F(A_2)$$

这样，我们就证明了 $\delta(A_2)=h_F(A_2)-h_A(A_2)$ 单调递减了。

于是我们可以预处理出 $\gamma(f_1,f_2)$，具体过程为二分出 $h_A,h_F$，然后二分出 $\delta$。

这里在预处理时的查询可能范围会到很大，所以预处理查询也带 log。

而且这里有一个很麻烦的事情就是说，我们查询的时候要求出最大的一个 $f_1$ 满足 $A_2\geq \gamma(f_1,f_2)$（为了快速处理非有用局面）。

$\gamma(f_1,f_2)$ 没有单调性（也有可能有），不能直接二分，要建个线段树，然后在线段树上二分。

同时 $f_1,f_2$ 在进攻防守时的交替次数是 $\log\log$ 次，但是证明这个实在过于困难，这里就不证了，有兴趣的同学可以来补充一下。

记 $F=\max(f_1,f_2)$，时间复杂度 $\mathcal{O}((Q+F^2\log^2F)\log n\log\log n)$。

Subtask 7

还能再再给力一点吗？

在刚才的简化中我们使用了很笨的一直防守，如果进攻呢？

一次进攻后手可能有很多种选择，只有当后手攻击力 $\leq$ 才能确定选择。

那么我们先防守 $x$ 次蓄力，然后发动攻击（$x$ 未知）。

此时还是无法确定后手的选择，但我们目的是降低后手的攻击力，提升 $\Delta_1$，然后进一步防守到攻击力大于 $S$。

后手有很多做法，不过可以规约为防守若干次（此时先手只能进攻）然后发动进攻，这样先手可以进行防守了。

无论怎么做，后手的攻击力不会超过 $A_2-(A_1+\Delta_1x)+f_2(S-(A_1+\Delta_1x))$。

同时我们发现前面还有 $A_2-A_1+\Delta_2\times f_2\leq S$ 的限制，因此：

$$A'_2=A_2-(A_1+\Delta_1x)+f_2(S-(A_1+\Delta_1x))$$ $$=A_2-A_1-(f_2+1)\Delta_1x+f_2\Delta_2$$ $$\leq S-(f_2+1)\Delta_1x$$

这可太好了！有 $\Delta'_1\geq (f_2+1)\Delta_1x$。

我们把 $\Delta'_1$ 增加了一个量级，但也付出了相应的代价：被后手攻击了一次（放成 $S$）。

再防守 $f_1-x$ 次就可以使攻击力至少变为 $(f_2+1)\Delta_1x(f_1-x)$，这个值如果超过 $2S$ 先手就可以直接获胜。

此时，我们令 $x=\dfrac{f_1}2$，就有：

$$\dfrac{1}4(f_2+1)\Delta_1f_1^2\leq 2S$$ $$(f_2+1)\Delta_1f_1^2\leq 8S$$

首先因为 0/1 状态的单调性可以把 $\Delta_2$ 记进状态。

然后 $f_1,\Delta_1,f_2$ 有多少种呢？

$$\sum\limits_{f_1=1}^D\dfrac{2S}{f_1^2}\ln\dfrac{2S}{f_1^2}$$

用积分近似或者用 $\sum\dfrac1{i^2}=\dfrac{\pi^2}{6}$ 都可以证明这个式子是 $\mathcal{O}(S\ln S)$ 的。

时间复杂度 $\mathcal{O}(S\log^2 S+q\log S)$。

Remark（Subtask Extra）（与正解无关）

还能再再再给力一点吗？

我们考虑将 Subtask6&7 的做法结合。

我们由 Sub6 知道，如果 $f_1,f_2$ 的可能性很小就好了。

我们的式子是 $(f_2+1)\Delta_1f_1^2\leq 8S$，那么，$\Delta_1$ 和 $f_2$，何如？

这个我们好像不知道，因为 $f_2$ 是对手的次数。

那么，假设现在先手乱防一通之后进入了一个有用的局面，之后发动进攻，这个时候后手有 $(f_1+1)\Delta_2f_2^2\leq 8S$。

这不就可以了吗，因为当前局面有用，所以 $\Delta_1\times f_1\leq \Delta_2$（Subtask 5 的结论），这样就有 $(f_1f_2)^2\leq 8S$ 了！

对于查询，我们直接枚举先手防守次数，这是 $\mathcal{O}(\sqrt{S})$ 的。

总时间复杂度 $\mathcal{O}((\log^2 S+q)\sqrt{S}\log S\log\log S)$。

Conclusion（与正解无关）

Extra 做法有点太 shaber 了，$q$ 沦落至和 $\log^2S$ 同级。

可以考虑设 $V$，对于 $f_2\leq V$ 我们求出所有的 $\gamma(f_1,f_2)$。

此时预处理时间复杂度为 $\sqrt{SV}\log^2S\log S\log\log S$。

然后查询时，如果 $f_2> V$ 我们才枚举防守次数，时间复杂度 $q\sqrt{\dfrac{S}V}\log S\log\log S$。

平衡一下，最后时间复杂度 $\mathcal{O}(\sqrt{qS}\log^2 S\log\log S)$。

这样的话，能做的范围会稍微大一点，同时 $q$ 和 $S$ 也能贴贴了！

Sub 7 的实现

```cpp
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define IV void
#define I i64
#define her1 20081214
#define cht 998244353
#define ull unsigned long long
#define mem(x,val) memset(x,val,sizeof x)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
ll read(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
	return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
map<tuple<i64,i64,i64>,i64>M;
i64 x;
bool dfs(i64 c1,i64 f1,i64 c2,i64 f2){
	bool flag=0;
	do{
		if(f2*x+c1<=0)return flag;
		if(f1*x+c2<=0||(c1>=x&&c2<=x))return!flag;
		if(c2>=x||!f2){
			c2-=c1;flag=!flag;
			swap(c1,c2),swap(f1,f2);
			continue;
		}
		if(c1<=0){
			if(!f1&&c2<x){
				i64 b2=x-c2,t=(-c1)/b2+1;
				if(t>f2)return flag;c1+=t*b2;f2-=t;continue;
			}
			i64 w1=max(min(-c1/x+!!(c1%x),c2<=0?-c2/x+!!(c2%x):0),0ll);
			w1=max(w1-1,0ll);c1+=x*(w1+1),c2+=w1*x,f1-=w1,f2-=1+w1;
			flag=!flag;swap(c1,c2),swap(f1,f2);continue;
		}
		if(c1>=0&&c2<=0)return !flag;
		i64 b1=x-c1,b2=x-c2;
		if(b2*f2>=b1)return !flag;
		if(b1*f1>=b2+c1){
			i64 t=floorl(((x*f1-b2)/(f1+1)-c1)/b2)+1;t=min(t,f2);
			if(!t){
				c1+=x,--f2;flag=!flag;
				swap(c1,c2),swap(f1,f2);
				continue;
			}
			c1+=t*b2,f2-=t;continue;
		}
		if(f2!=1&&(max({f1+1,b2,f2})>=8*x||(f1+1)*b2*f2*f2>=8*x))return !flag;
		if(M.count({f1,c2,f2}))return flag^(c1>=M[{f1,c2,f2}]);i64 l=0,r=x,a=x,mid;
		while(l<=r)
			mid=l+r>>1,(dfs(c2,f2-1,mid+x,f1)&&dfs(c2-mid,f2,mid,f1))?l=mid+1:(a=mid,r=mid-1);
		return M[{f1,c2,f2}]=a,flag^(c1>=a);
	}while(1);
}
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	x=read();i64 q=read();
	while(q--){
		i64 n1=read(),m1=read(),n2=read(),m2=read();
		puts(dfs(n1-m2*x,m1,n2-m1*x,m2)?"YES":"NO");
	}
	return 0;
}