B. Упоротые префиксные суммы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$a_1, a_2, \dots, a_n$$$ - отсортированная последовательность целых чисел длины $$$n$$$ такая, что $$$a_1 \leq a_2 \leq \dots \leq a_n$$$.

Для каждого $$$1 \leq i \leq n$$$, префиксная сумма $$$s_i$$$ первых $$$i$$$ элементов $$$a_1, a_2, \dots, a_i$$$ определяется как $$$$$$ s_i = \sum_{k=1}^i a_k = a_1 + a_2 + \dots + a_i. $$$$$$

Вам заданы последние $$$k$$$ элементов префиксных сумм, а именно $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$. Ваша задача определить, возможно ли это.

Формально, дано $$$k$$$ целых чисел $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$, задача состоит в том, чтобы проверить, есть ли последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ такая, что

  1. $$$a_1 \leq a_2 \leq \dots \leq a_n$$$, и
  2. $$$s_i = a_1 + a_2 + \dots + a_i$$$ для всех $$$n-k+1 \leq i \leq n$$$.
Входные данные

В первой строке содержится целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — Количество наборов входных данных. Затем следуют сами наборы входных данных.

В первой строке набора входных данных задано два целых числа $$$n$$$ ($$$1 \leq n \leq 10^5$$$) и $$$k$$$ ($$$1 \leq k \leq n$$$), означающие длину последовательности $$$a$$$ и число данных элементов префиксных сумм.

Во второй строке набора входных данных задано $$$k$$$ целых чисел $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$ ($$$-10^9 \leq s_i \leq 10^9$$$ для каждого $$$n-k+1 \leq i \leq n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек) если это возможно и «NO» (без кавычек) в противном случае.

Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут распознаны как положительный ответ).

Пример
Входные данные
4
5 5
1 2 3 4 5
7 4
-6 -5 -3 0
3 3
2 3 4
3 2
3 4
Выходные данные
Yes
Yes
No
No
Примечание

В первом наборе входных данных подходит только $$$a = [1, 1, 1, 1, 1]$$$.

Во втором наборе входных данных мы можем выбрать $$$a = [-3, -2, -1, 0, 1, 2, 3]$$$.

В третьем наборе входных данных подходит только $$$a = [2, 1, 1]$$$, но это не отсортированная последовательность.

В четвертом наборе входных данных может быть показано, что такой последовательности не существует.