Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Predict Outcome of the Game

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere are *n* games in a football tournament. Three teams are participating in it. Currently *k* games had already been played.

You are an avid football fan, but recently you missed the whole *k* games. Fortunately, you remember a guess of your friend for these *k* games. Your friend did not tell exact number of wins of each team, instead he thought that absolute difference between number of wins of first and second team will be *d*_{1} and that of between second and third team will be *d*_{2}.

You don't want any of team win the tournament, that is each team should have the same number of wins after *n* games. That's why you want to know: does there exist a valid tournament satisfying the friend's guess such that no team will win this tournament?

Note that outcome of a match can not be a draw, it has to be either win or loss.

Input

The first line of the input contains a single integer corresponding to number of test cases *t* (1 ≤ *t* ≤ 10^{5}).

Each of the next *t* lines will contain four space-separated integers *n*, *k*, *d*_{1}, *d*_{2} (1 ≤ *n* ≤ 10^{12}; 0 ≤ *k* ≤ *n*; 0 ≤ *d*_{1}, *d*_{2} ≤ *k*) — data for the current test case.

Output

For each test case, output a single line containing either "yes" if it is possible to have no winner of tournament, or "no" otherwise (without quotes).

Examples

Input

5

3 0 0 0

3 3 0 0

6 4 1 0

6 3 3 0

3 3 3 2

Output

yes

yes

yes

no

no

Note

Sample 1. There has not been any match up to now (*k* = 0, *d*_{1} = 0, *d*_{2} = 0). If there will be three matches (1-2, 2-3, 3-1) and each team wins once, then at the end each team will have 1 win.

Sample 2. You missed all the games (*k* = 3). As *d*_{1} = 0 and *d*_{2} = 0, and there is a way to play three games with no winner of tournament (described in the previous sample), the answer is "yes".

Sample 3. You missed 4 matches, and *d*_{1} = 1, *d*_{2} = 0. These four matches can be: 1-2 (win 2), 1-3 (win 3), 1-2 (win 1), 1-3 (win 1). Currently the first team has 2 wins, the second team has 1 win, the third team has 1 win. Two remaining matches can be: 1-2 (win 2), 1-3 (win 3). In the end all the teams have equal number of wins (2 wins).

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/16/2022 22:51:33 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|