B2. Коа и пляж (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственная разница между простой и сложной версиями заключается в ограничениях. В этой версии ограничения выше. Вы можете делать взломы только если обе версии задачи сданы.

Коала Коа на пляже!

Пляж состоит из (слева направо) берега, $$$n+1$$$ метров моря, и острова в $$$n+1$$$ метрах от берега.

Она измерила глубину моря на расстоянии $$$1, 2, \dots, n$$$ метров от берега и сохранила эту информацию в массиве $$$d$$$. $$$d_i$$$ обозначает глубину моря в $$$i$$$ метрах от берега для $$$1 \le i \le n$$$.

Как и на любом пляже, на этом есть прилив, интенсивность прилива измеряется параметром $$$k$$$ и влияет на все глубины с начала в момент времени $$$t=0$$$ следующим образом:

  • На протяжении $$$k$$$ секунд каждую секунду прилив увеличивает все глубины на $$$1$$$.

  • На протяжении следующих $$$k$$$ секунд каждую секунду прилив уменьшает все глубины на $$$1$$$.

  • Этот процесс повторяется снова и снова (т.е. глубина увеличивается на протяжении $$$k$$$ секунд, затем уменьшается на протяжении $$$k$$$ секунд и так далее ...).

    Формально, давайте определим $$$0$$$-индексированный массив $$$p = [0, 1, 2, \ldots, k - 2, k - 1, k, k - 1, k - 2, \ldots, 2, 1]$$$ длины $$$2k$$$. В момент времени $$$t$$$ ($$$0 \le t$$$) глубина на расстоянии $$$i$$$ метров от берега равна $$$d_i + p[t \bmod 2k]$$$ ($$$t \bmod 2k$$$ обозначает остаток от деления $$$t$$$ на $$$2k$$$). Обратите внимание, что изменения происходят мгновенно каждую секунду, см. примеры для лучшего понимания.

В момент времени $$$t=0$$$ Коа стоит на берегу, и хочет добраться до острова. Пусть во время $$$t$$$ ($$$0 \le t$$$) она находится в $$$x$$$ ($$$0 \le x \le n$$$) метрах от берега:

  • За одну секунду Коа может проплыть на $$$1$$$ метр дальше от берега ($$$x$$$ меняется на $$$x+1$$$) или вообще не плыть ($$$x$$$ остается неизменным), в обоих случаях $$$t$$$ меняется на $$$t+1$$$.

  • Поскольку Коа  — плохой пловец, глубина моря в точке, где она находится, не может превышать $$$l$$$ во все целые точки времени (или она утонет). Более формально, если Коа находится в $$$x$$$ ($$$1 \le x \le n$$$) метрах от берега в момент $$$t$$$ (для некоторого целого $$$t\ge 0$$$), то глубина моря в этой точке  — $$$d_x + p[t \bmod 2k]$$$ — не может превышать $$$l$$$. Другими словами, $$$d_x + p[t \bmod 2k] \le l$$$ должно выполняться всегда.

  • Когда Коа достигает острова в $$$n+1$$$ метров от берега, она останавливается и может отдохнуть.

    Обратите внимание, что пока Коа плывет, прилив не влияет на нее (то есть она не может утонуть во время плавания). Обратите внимание, что Коа может оставаться на берегу, сколько ей нужно, и ни берег, ни остров не подвержены влиянию прилива (это твердая земля, и она там не утонет).

Коа хочет знать, сможет ли она добраться с берега на остров. Помогите ей!

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

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$)  — количество наборов входных данных. Описание наборов входных данных приведено ниже.

Первая строка каждого набора входных данных содержит три целых числа: $$$n$$$, $$$k$$$ and $$$l$$$ ($$$1 \le n \le 3 \cdot 10^5; 1 \le k \le 10^9; 1 \le l \le 10^9$$$) — количество метров моря и параметры $$$k$$$ и $$$l$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ ($$$0 \le d_i \le 10^9$$$) — глубины каждого метра моря.

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

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

Для каждого набора входных данных:

Выведите Yes, если Коа сможет добраться от берега до острова, и No в обратном случае.

Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).

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

Ниже $$$s$$$ обозначает берег, $$$i$$$ обозначает остров, $$$x$$$ обозначает расстояние от Коа до берега, нижнее подчеркивание обозначает позицию Коа, а значения в массиве ниже обозначают текущие глубины, измененные под влиянием прилива, на расстояниях $$$1, 2, \dots, n$$$ от берега.

В наборе входных данных $$$1$$$ мы имеем $$$n = 2, k = 1, l = 1, p = [ 0, 1 ]$$$.

Коа хочет добраться с берега (c $$$x = 0$$$) на остров (c $$$x = 3$$$). Опишем возможное решение:

  • Первоначально в $$$t = 0$$$ пляж выглядит так: $$$[\underline{s}, 1, 0, i]$$$.
  • В $$$t = 0$$$, если бы Коа решила доплыть до $$$x = 1$$$, пляж выглядел бы так: $$$[s, \underline{2}, 1, i]$$$ в $$$t = 1$$$, и так как $$$2 > 1$$$ она бы утонула. Таким образом, Коа вместо этого ждет $$$1$$$ секунду, а пляж выглядит как $$$[\underline{s}, 2, 1, i]$$$ в $$$t = 1$$$.
  • В $$$t = 1$$$ Коа плывет до $$$x = 1$$$, пляж выглядит как $$$[s, \underline{1}, 0, i]$$$ в $$$t = 2$$$. Коа не тонет, потому что $$$1 \le 1$$$.
  • В $$$t = 2$$$ Коа плывет до $$$x = 2$$$, пляж выглядит как $$$[s, 2, \underline{1}, i]$$$ в $$$t = 3$$$. Коа не тонет, потому что $$$1 \le 1$$$.
  • В $$$t = 3$$$ Коа плывет до $$$x = 3$$$, пляж выглядит как $$$[s, 1, 0, \underline{i}]$$$ в $$$t = 4$$$.
  • В $$$t = 4$$$ Коа находится в $$$x = 3$$$, и она сделала это!

Можно показать, что наборе входных данных $$$2$$$ Коа не сможет доплыть до острова.