406714: GYM102503 K Shoedoku

Sasha, the suspiciously sassy Swiss, sells seashells by the seashores of Sorsogon. But being a businessperson by the beachfront becomes boring. So, Sasha sets up a scheme so that she has something to do to pass the time.

Sasha draws a giant $$$j \times g$$$ grid in the sand. She then makes $$$p$$$ pairs of paper shoes. Each pair possesses a particular pattern and no two pairs possess the same pattern. The goal is then to put the $$$2p$$$ paper shoes in such a way each of them is either exactly $$$c$$$ cells to the left, exactly $$$c$$$ cells to the right, exactly $$$c$$$ cells to the top or exactly $$$c$$$ cells to the bottom of its pair. A clarification: each cell must contain at most one shoe. As the perusing programmer of this problem, we petition you to pronounce if it is possible to achieve this ambition.

Fun fact: Sasha, the suspiciously sassy Swiss selling seashells by the seashores of Sorsogon, decided that the distance of the $$$p$$$ pairs of paper shoes should be $$$c$$$ cells as she was selling seashells.

The first line of input contains $$$t$$$, the number of test cases.

Each test case consists of a single line containing four space-separated integers $$$j, g, c, p$$$.

For each test case, output a single line containing a single string which is one of the following:

• YAY if it is possible to put the $$$2p$$$ paper shoes;
• NAY otherwise.

$$$1 \le t \le 10^5$$$

$$$1 \le j, g, c, p \le 10^{18}$$$

Subtask 1 (17 points):

$$$t \le 500$$$

$$$j, g \le 5$$$

$$$p \le 10^6$$$

Subtask 2 (7 points):

$$$t \le 10^4$$$

$$$j, g \le 5$$$

$$$p \le 10^6$$$

Subtask 3 (22 points):

$$$j, g \le 10$$$

$$$p \le 10^6$$$

Subtask 4 (21 points):

$$$t \le 200$$$

$$$j, g \le 500$$$

$$$p \le 10^6$$$

Subtask 5 (17 points):

$$$j, g \le 10^9$$$

Subtask 6 (16 points):

No additional constraints.

2
1 2 1 1
3 3 2 3

YAY
YAY