Points

Time limit1sMemory limit128 MB

Summary

Determine reachability of points under a closure of shift, halving-when-even, and transitivity rules starting from one point, essentially characterizing (x,y) pairs by an invariant like x-y modulo constraints and gcd-related structure.

Level: Hard8 of 10
Topics: Math, Number theory, Graph
Solved: No attempts yet

Problem

Let S be a set of points with natural-number coordinates on the coordinate plane. Initially, S contains exactly one point (a, b). You may repeatedly apply any of the following rules, in any order, and add the newly created point to S.

Rule 1: If (x, y) is in S, add (x + 1, y + 1) to S.
Rule 2: If (x, y) is in S and both x and y are even, add (x / 2, y / 2) to S.
Rule 3: If both (x, y) and (y, z) are in S, add (x, z) to S.

Given the initial point (a, b), determine for each queried point (p, q) whether it can be added to S by repeatedly applying these rules.

Input

The first line contains two natural numbers a and b, the coordinates of the point initially in S.

Each of the next five lines contains two natural numbers p and q, the coordinates of one queried point.

All coordinates in the input are between 1 and 100,000, inclusive.

Output

For the five queried points, output whether each point can be created by repeatedly applying the three rules.

For each query, print Y if it can be created, and N otherwise, one answer per line in input order.

Examples1

Example 1
Input
```
3 5
4 6
2 3
1 1
2 5
4 7
```
Expected output
```
Y
Y
N
Y
Y
```