Яблоки по корзинам

У Саши есть $n$ яблок с целыми весами $w\_1, w\_2, \ldots, w\_n$, которые лежат на столе, а также две вместительные корзины.

Саша выбирает целое число $k$ и рассматривает яблоки с весом не больше $k$. После этого она может положить каждое яблоко с весом $w\_i \le k$ в одну из двух корзин, либо оставить его на столе. Яблоки с весом $w\_i > k$ в любом случае остаются на столе.

Назовем пару чисел $(x, y)$ $k$-достижимой, если Саша может положить некоторые яблоки с весом не больше $k$ в корзины так, чтобы сумма весов яблок в первой корзине оказалась равна $x$, а сумма весов яблок во второй корзине оказалась равна $y$. Назовем пару чисел $(a, b)$ $k$-идеальной, если для всех $x$ и $y$, где $0 \le x \le a$ и $0 \le y \le b$, пара $(x, y)$ является $k$-достижимой.

Саша рассматривает $q$ троек чисел $k$, $a$, $b$ и для каждой из них хочет понять, является ли $k$-идеальной пара $(a, b)$.

В первой строке даны два целых числа $n$ и $q$ --- количество яблок, которые есть у Саши, и количество запросов, которые вам надо обработать ($1 \le n, q \le 300\\,000$).

Во второй строке даны $n$ целых чисел $w\_1$, $w\_2$, $\dots$, $w\_n$ --- веса яблок, которые есть у Саши ($1 \le w\_i \le 10^{12}$).

В третьей строке находится целое число $z$, которое используется для формирования запросов, на которые необходимо ответить ($0 \le z \le 10^6$).

В следующих $q$ строках даны описания запросов. Запросы пронумерованы от $1$ до $q$. Каждая строка содержит три целых числа $j$, $c$ и $d$ ($0 \le j, c, d \le 10^{18}$). Запрос формируется из чисел в этой строке по следующим правилам. Вычислим $v$, как сумму номеров запросов, сделанных до текущего, для которых заданная в запросе пара $(a, b)$ оказалась $k$-идеальной. Тогда в текущем запросе $k = j - v\cdot z$; $a = c - v \cdot z$; $b = d - v \cdot z$. Гарантируется, что $k, a, b \geq 0$.

Обратите внимание, что при $z = 0$ (что верно для большинства подзадач), значения $k$, $a$ и $b$ равны $j$, $c$ и $d$ соответственно. То есть параметры запроса не зависят от ответов на предыдущие запросы и даны во входных данных в явном виде.

На каждый запрос выведите <<Yes>>, если пара $(a, b)$ в данном запросе является $k$-идеальной, иначе выведите <<No>>.