BTCODE_A - Traversing Grid

Given 2 points in 2 dimensional space (xs, ys) and (xd, yd), your task is to find whether (xd, yd) can be reached from (xs, ys) by making a sequence of zero or more operations.

From a given point (x, y), the operations possible are:

  • Move to point (y, x)
  • Move to point (x, -y)
  • Move to point (x + y, y)
  • Move to point (2 * x, y)

Input

The first line of input contains T, the number of test cases. T lines follow, one for each test case. For each test case, the input contains one line denoting the 4 integers xs, ys, xd, yd

Output

Output T lines, one for each test case. For each test case, output "YES" if (xd, yd) is reachable from (xs, ys) and "NO" otherwise. (quotes for clarity)

Example

Input:
1
1 1 2 2

Output:
YES

Constraints

T <= 25

-10^10 <= xs, ys, xd, yd <= 10^10

Note that, although the input values are constrained by the above inequality, the coordinates of the points at the intermediate steps need not be.

Explanation

Test case 1: We can move in the following manner: (1,1) → (2,1), using the operation (x, y) → (2 * x, y). Then, move from (2, 1) → (1, 2), using the operation (x, y) → (y, x). Finally use the operation (x, y) → (2 * x, y) to move from (1, 2) → (2, 2).


Added by:suhash
Date:2011-02-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2011, NIT Trichy, India

hide comments
2018-06-07 01:51:48
Taking the usual suspects lightly costed me 40mins of staring at the screen wondering WTF. Good problem, fun to visualize and figure out.
2016-06-11 15:22:49 Piyush Kumar
Can somebody provide more test cases?
2014-06-25 21:35:00 5star
Great question :)
2012-09-02 15:20:51 Amit Kumar
Tricky test cases please...

@suhash tell me why my code (7580002)
is wrong
2012-01-13 15:44:39 Ajey Golsangi
Good one.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.