A. Dinner Time
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given four integers $$$n$$$, $$$m$$$, $$$p$$$, and $$$q$$$, determine whether there exists an integer array $$$a_1, a_2, \ldots, a_n$$$ (elements may be negative) satisfying the following conditions:

  • The sum of all elements in the array is equal to $$$m$$$: $$$$$$a_1 + a_2 + \ldots + a_n = m$$$$$$
  • The sum of every $$$p$$$ consecutive elements is equal to $$$q$$$: $$$$$$a_i + a_{i + 1} + \ldots + a_{i + p - 1} = q,\qquad\text{ for all }1\le i\le n-p+1$$$$$$
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first and only line of each test case contains four integers $$$n$$$, $$$m$$$, $$$p$$$, and $$$q$$$ ($$$1 \le p \le n \le 100$$$, $$$1 \le q, m \le 100$$$) — the length of the array, the sum of elements, the length of a segment, and the sum of a segment, respectively.

Output

For each test case, output "YES" (without quotes) if there exists an array satisfying the above conditions, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes", and "Yes" will all be recognized as valid responses).

Example
Input
5
3 2 2 1
1 1 1 1
5 4 2 3
10 7 5 2
4 4 1 3
Output
YES
YES
YES
NO
NO
Note

In the first test case, an example of an array satisfying the condition is $$$[1, 0, 1]$$$. This is because:

  • $$$a_1+a_2+a_3 = 1+0+1 = 2 = m$$$
  • $$$a_1+a_2=1+0=1=q$$$
  • $$$a_2+a_3=0+1=1=q$$$

In the second test case, the only array satisfying the condition is $$$[1]$$$.

In the third test case, an example of an array satisfying the condition is $$$[-2, 5, -2, 5, -2]$$$.

In the fourth test case, it can be proven that there is no array satisfying the condition.