Problem Description

JOI Avenue is an east-west road with length $L$ meters. A location $l$ is the point that is $l\ (0 \leq l \leq L)$ meters from the west end of the road.

This year, a marathon event is held on JOI Avenue for the first time. The rules of this marathon are different from usual, and it is run in the following way:

• There are $N$ balls placed on the road. The $i\ (1 \leq i \leq N)$-th ball is placed at location $X_{i}$. There may be multiple balls placed at the same location.
• A participant starts from the designated start point, collects all $N$ balls, and is considered to have finished if they reach the designated goal point within the designated time limit. However, if they put down any collected ball on the ground, they will be disqualified.

The start point, goal point, and time limit of this event have not been announced yet, but $Q$ possible plans have been announced. In the $j\ (1 \leq j \leq Q)$-th plan, the start point is location $S_{j}$, the goal point is location $G_{j}$, and the time limit is $T_{j}$ seconds.

Rie is one of the athletes in the marathon event. It takes her $1$ second to pick up one ball, and running $1$ meter on the road while carrying $x$ balls takes $x+1$ seconds.

Given the information about JOI Avenue, the balls, and the plans, write a program to determine for each plan whether Rie can finish.

Input Format

The first line contains two integers $N, L$.

The second line contains $N$ integers $X_1, X_2, \ldots ,X_N$ separated by spaces.

The third line contains one integer $Q$.

The next $Q$ lines each contain three integers $S_j, G_j, T_j$, representing the $j$-th plan.

Output Format

Output $Q$ lines. On the $j\ (1 \leq j \leq Q)$-th line, output Yes if Rie can finish in the $j$-th plan; otherwise output No.

3 100
30 80 30
3
0 100 403
0 100 300
0 100 262

Yes
Yes
No

3 100
30 80 30
3
0 0 403
0 0 300
0 0 262

Yes
No
No

6 100
0 50 100 0 50 100
4
20 70 600
70 20 600
10 40 600
40 10 600

No
Yes
No
Yes

Hint

For all input data, the following conditions are satisfied:

• $1 \leq N \leq 5\times 10^5$
• $1 \leq L \leq 5\times 10^5$
• $0 \leq X_{i} \leq L\ (1 \leq i \leq N)$
• $1 \leq Q \leq 5\times 10^5$
• $0 \leq S_{j} \leq L\ (1 \leq j \leq Q)$
• $0 \leq G_{j} \leq L\ (1 \leq j \leq Q)$
• $1 \leq T_{j} \leq 5\times 10^5\ (1 \leq j \leq Q)$

The detailed additional constraints and scores for subtasks are shown in the table below.

Translated by ChatGPT 5