Doremy 居住在一个由 $n$ 个城市组成的国家，城市编号为 $1$ 到 $n$，第 $i$ 个城市里居住着 $a_i$ 个人。这可以被建模为一个含有 $n$ 个节点的无向图。

起初，图中没有任何边。现在 Doremy 想要让这个图连通。

为此，如果满足以下条件，她可以在 $i$ 和 $j$ 之间添加一条边：

$$\sum_{k \in S} a_k \ge i \cdot j \cdot c$$

其中 $S$ 是当前与 $i$ 或 $j$ 处于同一个连通分量的所有节点的集合，而 $c$ 是一个给定的常数。

Doremy 能否让这个图连通？

如果存在一条从 $i$ 到 $j$ 的路径，则称两个节点 $(i, j)$ 处于同一个连通分量中。如果一个图的所有节点都处于同一个连通分量中，则称该图是连通的。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, c$ ($2 \le n \le 2 \cdot 10^5$, $1 \le c \le 10^6$) — 节点数量和常数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{12}$) — 居住在第 $i$ 个城市的人数。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果可以使图连通，则输出 "YES"（不带引号），否则输出 "NO"（不带引号）。

你可以输出任意大小写的字母（大写或小写）。

样例

输入样例 1

7
4 10
0 20 15 10
2 1
1 1
5 1
0 1 0 4 199
5 2
1 1 3 1 1
5 5
5 6 1 10 2
5 1000000
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
3 1
0 0 2

输出样例 1

Yes
Yes
Yes
No
No
Yes
No

说明

在第一个测试用例中，Doremy 可以按以下顺序加边：

1. 添加 $(1, 2)$。此操作是合法的，因为 $a_1 + a_2 = 20 \ge i \cdot j \cdot c = 20$。
2. 添加 $(1, 3)$。此操作是合法的，因为 $a_1 + a_2 + a_3 = 35 \ge i \cdot j \cdot c = 30$。
3. 添加 $(1, 4)$。此操作是合法的，因为 $a_1 + a_2 + a_3 + a_4 = 45 \ge i \cdot j \cdot c = 40$。

在第二个测试用例中，Doremy 可以添加边 $(1, 2)$，因为 $a_1 + a_2 = 2 \ge 1 \cdot 2 \cdot 1$。在此之后，图就是连通的。

在第三个测试用例中，Doremy 可以按照 $(5, 4)$，$(5, 3)$，$(5, 2)$ 和 $(5, 1)$ 的顺序添加边。

在第四个测试用例中，Doremy 无法添加任何边。