[latexpage]

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

给你一对数a,b，你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。

说明：这里的拼就是使得你选出的向量之和为(x,y)

 

Input

第一行数组组数t，(t<=50000)

接下来t行每行四个整数a,b,x,y  (-2*10⁹<=a,b,x,y<=2*10⁹)

Output

 

t行每行为Y或者为N，分别表示可以拼出来，不能拼出来

Sample Input

3

2 1 3 3

1 1 0 1

1 0 -2 3

Sample Output

Y

N

Y

HINT

样例解释：

第一组：(2,1)+(1,2)=(3,3)

第三组：(-1,0)+(-1,0)+(0,1)+(0,1)+(0,1)=(-2,3)

Solution

这题我们可以发现向量$(-a,-b)=(a,b)*-1$,$(-b,-a)=(b,a)*-1$,$(b,-a)=-1*(-b,a)$,$(-a,b)=-1*(a,-b)$,所以我们可以发现我们只需要用4个向量$(a,b),(b,a),(-b,a),(a,-b)$就够了。
设$(x,y)=x1*(a,b)+x2*(b,a)+x3*(-b,a)+x4*(a,-b)$
则我们可以得到方程$\begin{cases}(x1+x4)*a+(x2-x3)*b=x\cr(x2+x3)*a+(x1-x4)*b=y\end{cases}$
再令$f1=x1+x4,f2=x2-x3,f3=x2+x3,f4=x1-x4$
则方程变为$\begin{cases}f1*a+f2*b=x\cr f3*a+f4*b=y\end{cases}$
我们可以发现，要使$x1,x2,x3,x4$有整数解，则$f1+f4$和$f2+f3$均应为偶数。
然后我们只需求出$f1,f2,f3,f4$即可，不难发现，我们可以用扩展欧几里得来解决。
则$\begin{cases}f1=X*\frac{x}{gcd(a,b)}+\frac{b}{gcd(a,b)}*t\cr f2=Y*\frac{x}{gcd(a,b)}-\frac{a}{gcd(a,b)}*t\end{cases}$(t为整数)
其中的X,Y为扩欧(这里求的方程为aX+bY=gcd(a,b)，所以需要将X,Y乘以$\frac{x}{gcd(a,b)}$)得到的一组解，同时可以发现当$ gcd(a,b)\nmid x$时，就没有整数解了。
同理可得第二个方程$\begin{cases}f3=X*\frac{y}{gcd(a,b)}+\frac{b}{gcd(a,b)}*p\cr f4=Y*\frac{y}{gcd(a,b)}-\frac{a}{gcd(a,b)}*p\end{cases}$(p为整数)

然后我们就得到了$\begin{cases}f1+f4=X*\frac{x}{gcd(a,b)}+Y*\frac{y}{gcd(a,b)}+\frac{b}{gcd(a,b)}*t-\frac{a}{gcd(a,b)}*p\cr f2+f3=X*\frac{y}{gcd(a,b)}+Y*\frac{x}{gcd(a,b)}+\frac{b}{gcd(a,b)}*p-\frac{a}{gcd(a,b)}*t\end{cases}$
可以发现，$f1+f4和f2+f3$的奇偶性与$t和p$的值有关，然后我们又可以由奇偶性发现，我们只需要判断$t=0,p=0; t=1,p=0; t=0,p=1; t=1,p=1$这四种情况即可！