사과를 바구니에 나누기

사샤에게는 무게가 정수인 사과 $n$개가 있고, 사과는 탁자 위에 놓여 있습니다. 또 사샤에게는 넉넉한 크기의 바구니 두 개가 있습니다.

사샤는 정수 $k$를 고르고, 무게가 $k$ 이하인 사과를 살펴봅니다. 무게가 $w_i \le k$인 각 사과는 두 바구니 중 하나에 넣거나 탁자 위에 그대로 둘 수 있습니다. 무게가 $w_i > k$인 사과는 항상 탁자 위에 남습니다.

두 수의 쌍 $(x, y)$는, 사샤가 무게가 $k$ 이하인 사과 일부를 바구니에 넣어 첫 번째 바구니의 무게 합이 $x$, 두 번째 바구니의 무게 합이 $y$가 되게 할 수 있을 때 $k$-도달 가능하다고 합니다.

쌍 $(a, b)$는, $0 \le x \le a$이고 $0 \le y \le b$인 모든 $x$, $y$에 대해 $(x, y)$가 $k$-도달 가능할 때 $k$-이상적이라고 합니다.

사샤는 수 세 개로 이루어진 $k$, $a$, $b$ 질의를 $q$개 가지고 있습니다. 각 질의마다 쌍 $(a, b)$가 $k$-이상적인지 알고 싶어 합니다.

첫 줄에 사과의 개수 $n$과 질의의 개수 $q$가 주어집니다 ($1 \le n, q \le 300\,000$).

둘째 줄에 사과의 무게 $w_1, w_2, \dots, w_n$이 주어집니다 ($1 \le w_i \le 10^{12}$).

셋째 줄에 질의를 만드는 데 쓰이는 정수 $z$가 주어집니다 ($0 \le z \le 10^6$).

이어지는 $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 \ge 0$이 보장됩니다.

$z = 0$이면(대부분의 부분 문제가 이 경우입니다) $k$, $a$, $b$는 각각 $j$, $c$, $d$와 같습니다. 이 경우 질의 값은 이전 답에 따라 달라지지 않고 입력에 그대로 주어집니다.

각 질의에 대해 쌍 $(a, b)$가 $k$-이상적이면 Yes를, 그렇지 않으면 No를 출력하세요.