Саша ma $n$ jabłek o całkowitych wagach $w_1,w_2,\ldots,w_n$, leżących na stole, oraz dwa pojemne kosze.

Саша wybiera liczbę całkowitą $k$ i rozpatruje jabłka o wadze nie większej niż $k$. Następnie może każde jabłko o wadze $w_i\le k$ włożyć do jednego z dwóch koszy albo pozostawić na stole. Jabłka o wadze $w_i>k$ w każdym przypadku pozostają na stole.

Parę liczb $(x,y)$ nazwiemy $k$-osiągalną, jeśli Саша może włożyć pewne jabłka o wadze nie większej niż $k$ do koszy tak, aby suma wag jabłek w pierwszym koszu wynosiła $x$, a w drugim $y$. Parę liczb $(a,b)$ nazwiemy $k$-idealną, jeśli dla wszystkich $x$ i $y$ spełniających $0\le x\le a$ i $0\le y\le b$ para $(x,y)$ jest $k$-osiągalna.

Саша rozpatruje $q$ trójek liczb $k,a,b$ i dla każdej chce ustalić, czy para $(a,b)$ jest $k$-idealna.

Wejście

W pierwszym wierszu podane są dwie liczby całkowite $n$ i $q$: liczba jabłek, które ma Саша, oraz liczba zapytań, które należy przetworzyć ($1\le n,q\le300\,000$).

W drugim wierszu podanych jest $n$ liczb całkowitych $w_1,w_2,\ldots,w_n$, wagi jabłek, które ma Саша ($1\le w_i\le10^{12}$).

W trzecim wierszu znajduje się liczba całkowita $z$, używana do tworzenia zapytań, na które należy odpowiedzieć ($0\le z\le10^6$).

W następnych $q$ wierszach podane są opisy zapytań. Zapytania są ponumerowane od $1$ do $q$. Każdy wiersz zawiera trzy liczby całkowite $j,c,d$ ($0\le j,c,d\le10^{18}$). Zapytanie tworzy się z liczb w tym wierszu według następujących reguł. Obliczmy $v$ jako sumę numerów zapytań wykonanych przed bieżącym, dla których podana w zapytaniu para $(a,b)$ była $k$-idealna. Wówczas w bieżącym zapytaniu $k=j-v\cdot z$, $a=c-v\cdot z$, $b=d-v\cdot z$. Gwarantuje się, że $k,a,b\ge0$.

Zwróć uwagę, że przy $z=0$ (co zachodzi w większości podzadań) wartości $k,a,b$ są równe odpowiednio $j,c,d$. Innymi słowy, parametry zapytania nie zależą od odpowiedzi na poprzednie zapytania i są podane wprost na wejściu.

Wyjście

Dla każdego zapytania wypisz Yes, jeśli para $(a,b)$ w tym zapytaniu jest $k$-idealna, a w przeciwnym przypadku wypisz No.

Podzadania

Przykład

Wejście 1

8 5
17 1 3 2 100 5 6 1
0
6 15 3
9 4 4
5 15 3
17 34 1
16 33 2

Wyjście 1

Yes
No
No
Yes
No

Wejście 2

8 5
17 1 3 2 100 5 6 1
1
6 15 3
10 5 5
6 16 4
18 35 2
21 38 7

Wyjście 2

Yes
No
No
Yes
No