Саша에게는 정수 무게 $w_1,w_2,\ldots,w_n$을 가진 사과 $n$개가 탁자 위에 놓여 있고, 넉넉한 크기의 바구니 두 개도 있다.
Саша는 정수 $k$를 선택하고 무게가 $k$ 이하인 사과들을 살펴본다. 그다음 무게가 $w_i\le k$인 각 사과를 두 바구니 중 하나에 넣거나 탁자 위에 그대로 둘 수 있다. 무게가 $w_i>k$인 사과는 언제나 탁자 위에 남는다.
Саша가 무게가 $k$ 이하인 사과 중 일부를 바구니에 넣어 첫 번째 바구니에 든 사과의 무게 합을 $x$, 두 번째 바구니에 든 사과의 무게 합을 $y$로 만들 수 있다면, 수의 쌍 $(x,y)$를 $k$-도달 가능하다고 하자. $0\le x\le a$, $0\le y\le b$인 모든 $x$와 $y$에 대해 $(x,y)$가 $k$-도달 가능하다면, 수의 쌍 $(a,b)$를 $k$-이상적이라고 하자.
Саша는 $k,a,b$로 이루어진 수의 삼중항 $q$개를 살펴보고, 각각에 대해 쌍 $(a,b)$가 $k$-이상적인지 알고 싶다.
입력
첫 번째 줄에 정수 $n$과 $q$가 주어진다. 각각 Саша가 가진 사과의 개수와 처리해야 할 질의의 개수이다 ($1\le n,q\le300\,000$).
두 번째 줄에 정수 $n$개 $w_1,w_2,\ldots,w_n$이 주어진다. Саша가 가진 사과의 무게이다 ($1\le w_i\le10^{12}$).
세 번째 줄에 정수 $z$가 주어진다. 이 수는 답해야 할 질의를 구성하는 데 사용된다 ($0\le z\le10^6$).
다음 $q$개 줄에 질의의 설명이 주어진다. 질의는 $1$부터 $q$까지 번호가 매겨져 있다. 각 줄은 정수 $j,c,d$ 세 개를 포함한다 ($0\le j,c,d\le10^{18}$). 이 줄의 수들로부터 다음 규칙에 따라 질의를 구성한다. 현재 질의보다 앞서 수행된 질의 중, 질의에 주어진 쌍 $(a,b)$가 $k$-이상적이었던 질의들의 번호의 합을 $v$라고 하자. 그러면 현재 질의에서 $k=j-v\cdot z$, $a=c-v\cdot z$, $b=d-v\cdot z$이다. $k,a,b\ge0$임이 보장된다.
대부분의 서브태스크에서 성립하는 $z=0$인 경우, $k,a,b$의 값은 각각 $j,c,d$와 같다는 점에 유의하라. 즉, 질의의 매개변수는 이전 질의의 답에 의존하지 않으며 입력에 명시적으로 주어진다.
출력
각 질의에 대해 주어진 쌍 $(a,b)$가 $k$-이상적이면 Yes를, 그렇지 않으면 No를 출력한다.
서브태스크
| 서브태스크 | 점수 | 추가 제한: $n,q$ | 추가 제한: $a,b$ | 추가 제한: $k$ | 추가 제한: $z$ | 필요한 서브태스크 |
|---|---|---|---|---|---|---|
| $1$ | $9$ | $n,q\le10$ | $z=0$ | |||
| $2$ | $6$ | $n\le100$ | $a\le100\,000$, $b=0$ | $k=10^{18}$ | $z=0$ | |
| $3$ | $3$ | $b=0$ | $k=10^{18}$ | $z=0$ | $2$ | |
| $4$ | $6$ | $n,q\le100$ | $a,b\le300$ | $k=10^{18}$ | $z=0$ | |
| $5$ | $6$ | $n\le100$ | $a,b\le300$ | $k=10^{18}$ | $z=0$ | $4$ |
| $6$ | $2$ | $n\le1\,500$ | $a,b\le1\,500$ | $k=10^{18}$ | $z=0$ | $4\text{–}5$ |
| $7$ | $6$ | $n\le5\,000$ | $a,b\le5\,000$ | $k=10^{18}$ | $z=0$ | $4\text{–}6$ |
| $8$ | $2$ | $a,b\le200\,000$ | $k=10^{18}$ | $z=0$ | $2,4\text{–}7$ | |
| $9$ | $9$ | $k=10^{18}$ | $z=0$ | $2\text{–}8$ | ||
| $10$ | $3$ | $b=0$ | $z=0$ | $2\text{–}3$ | ||
| $11$ | $6$ | $n,q\le100$ | $a,b\le300$ | $z=0$ | $4$ | |
| $12$ | $6$ | $n\le100$ | $a,b\le300$ | $z=0$ | $4\text{–}5,11$ | |
| $13$ | $2$ | $n,q\le1\,500$ | $a,b\le1\,500$ | $z=0$ | $4,11$ | |
| $14$ | $2$ | $n\le1\,500$ | $a,b\le1\,500$ | $z=0$ | $4\text{–}6,11\text{–}13$ | |
| $15$ | $6$ | $n\le5\,000$ | $a,b\le5\,000$ | $z=0$ | $4\text{–}7,11\text{–}14$ | |
| $16$ | $2$ | $a,b\le200\,000$ | $z=0$ | $4\text{–}8,11\text{–}15$ | ||
| $17$ | $6$ | $z=0$ | $1\text{–}16$ | |||
| $18$ | $18$ | 예제, $1\text{–}17$ |
예제
입력 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
출력 1
Yes No No Yes No
입력 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
출력 2
Yes No No Yes No