Description

$Dlee$ 最近在玩一个叫 $Climb Staris$ 的游戏。游戏中有一座层数为 $n$ 的塔，$Dlee$ 开始时在 $0$ 层，其余 $1,2,3\dots n$ 各有一个怪物，每个怪物都有一个血量 $a_i$，当然 $Dlee$ 也有一个初始攻击力 $a_0$。$Dlee$ 每次移动可以从当前层向上跳 $k$ 层或往下走 $1$ 层（已经走过的就不能再走了）。

$Dlee$ 从当前层移动到其它层的条件是：

1. 目标层数不超过 $Dlee$ 的最大移动距离
2. $Dlee$ 的攻击力大于等于目标层怪物血量

$Dlee$ 每到达新的一层都会击杀怪物并增加相当于怪物血量的攻击力

请问 $Dlee$ 能否击杀所有怪物

Input Format

有 $T$ 组样例，第一行输入一个整数 $T$

对于每组样例，第一行输入三个整数 $n, a_0, k$（$1\le n,k\le 10^5,1\le a_0\le 10^9$) 含义与题面描述相同，第二行输入 $n$ 个整数 $a_1,a_2\dots a_n$ 表示第 $i$ 层的怪物血量。

对于所有样例 $n$ 的总和不超过 $1e6$

Output Format

对于每组样例在单独一行输出，能击杀所有怪物输出YES否则输出NO

4
6 1 4
2 2 1 1 9 3
4 2 2
2 3 8 1
3 1 2
3 1 2
7 2 3
4 3 2 7 20 20 20

YES
YES
NO
NO

Source

Online Judge http://127.0.0.1