D. 【入门】构造数组

    传统题 100ms 256MiB

【入门】构造数组

比赛已经结束。新提交将被视为补题提交,不计入比赛成绩。

题目描述

给定四个整数 nn 、 mm 、 pp 和 qq ,判断是否存在满足以下条件的整数数组 a1,a2,…,ana_1, a_2, \ldots, a_n (元素可能为负数):

  • 数组中所有元素的和等于 mm :

    a1+a2+…+an=ma_1 + a_2 + \ldots + a_n = m
  • 每 pp 个连续元素之和等于 qq :

    $$a_i + a_{i + 1} + \ldots + a_{i + p - 1} = q,\qquad\text{ for all }1\le i\le n-p+1$$

输入格式

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 tt ( 1≤t≤1041 \le t \le 10^4 )。测试用例说明如下。

每个测试用例的第一行也是唯一一行包含四个整数 nn 、 mm 、 pp 和 qq ( 1≤p≤n≤1001 \le p \le n \le 100 、 1≤q,m≤1001 \le q, m \le 100 )--分别是数组的长度、元素的总和、段的长度和段的总和。

输出格式

输出

对于每个测试用例,如果存在满足上述条件的数组,则输出 "YES"(不带引号),否则输出 "NO"(不带引号)。

5
3 2 2 1
1 1 1 1
5 4 2 3
10 7 5 2
4 4 1 3
YES
YES
YES
NO
NO

数据范围与提示

【样例 1 解释】

在第一个测试用例中,满足条件的数组示例是 [1,0,1][1, 0, 1] 。这是因为

  • a1+a2+a3=1+0+1=2=ma_1+a_2+a_3 = 1+0+1 = 2 = m
  • a1+a2=1+0=1=qa_1+a_2=1+0=1=q
  • a2+a3=0+1=1=qa_2+a_3=0+1=1=q

在第二个测试用例中,唯一满足条件的数组是 [1][1] 。

在第三个测试用例中,满足条件的数组是 [−2,5,−2,5,−2][-2, 5, -2, 5, -2] 。

在第四个测试用例中,可以证明没有满足条件的数组。

【数据范围】

  • 1≤t≤1041 \le t \le 10^4
  • 1≤p≤n≤1001 \le p \le n \le 100 、 1≤q,m≤1001 \le q, m \le 100