Marathon Race 2

JOI Avenue is a road of length $L$ in an east-west direction. The place of $l$ meters ($0 ≤ l ≤ L$) from the west end on the road is called ”position $l$”.

The first marathon race in JOI Avenue is going to be held this year. The race has a different regulation from normal one, which is described in the following:

• Before the race, $N$ balls are located on the road. The $i$-th ball ($1 ≤ i ≤ N$) is located at position $X_i$. Multiple balls may be located at the same position.
• The participant starts at the designated position.
• The participant collects all $N$ balls and finishes at the designated position. When this is achieved within the designated time limit, one completes the race. However, once the participant collect a ball, they must not put the ball on the road, otherwise they will be disqualified from the race.

The starting and finishing position, and the time limit, are not yet announced, but it is known that they are chosen from $Q$ scenarios. The $j$-th scenario ($1 ≤ j ≤ Q$) is that, the participant starts at position $S_j$, finishes at position $G_j$, and the time limit is $T_j$ seconds.

Rie is participating in the marathon race. She spends $1$ second to collect $1$ ball. She spends $x + 1$ seconds to move $1$ meter, where $x$ is the number of balls she is carrying.

Write a program which, given the information of JOI Avenue, the positions of balls, and the scenarios, determines whether there exists a way for Rie to complete the race, for each scenario.

Read the following data from the standard input.

$N$ $L$

$X_1$ $X_2$ $\cdots$ $X_N$

$Q$

$S_1$ $G_1$ $T_1$

$S_2$ $G_2$ $T_2$

$\vdots$

$S_Q$ $G_Q$ $T_Q$

Write $Q$ lines to the standard output. On the $j$-th line ($1 ≤ j ≤ Q$), output Yes if there exists a way for Rie to complete the race for scenario $j$, and No otherwise.

• $1 ≤ N ≤ 500\, 000$.
• $1 ≤ L ≤ 500\, 000$.
• $0 ≤ X_i ≤ L$ ($1 ≤ i ≤ N$).
• $1 ≤ Q ≤ 500\, 000$.
• $0 ≤ S_j ≤ L$ ($1 ≤ j ≤ Q$).
• $0 ≤ G_j ≤ L$ ($1 ≤ j ≤ Q$).
• $1 ≤ T_j ≤ 500\, 000$ ($1 ≤ j ≤ Q$).
• Given values are all integers.