JOI Marathon Challenge

This problem takes place on JOI Avenue – an east–west road of length \(L\) meters. On the road, there are \(N\) balls placed at various locations \(X_i\) (multiple balls may share the same location). In the marathon, a participant starts from a given starting position \(S\), must collect all \(N\) balls (picking up each ball takes 1 second) without ever dropping a ball, and then finish at the goal position \(G\) within a time limit \(T\) seconds.

The twist is that while running with \(x\) balls in hand, the time to run 1 meter is \(x+1\) seconds. Hence, the order in which the balls are collected affects the overall time: in order to minimize the extra cost incurred by carrying balls, it is best to postpone picking them up for as long as possible. Note that the participant is free to choose any order to collect the balls.

Formally, given:

• A road of length \(L\) meters, where any point on the road is denoted by the distance in meters from the west end.
• \(N\) balls placed at positions \(X_1, X_2, \dots, X_N\) (\(0 \le X_i \le L\)).
• \(Q\) proposals. The \(j\)-th proposal specifies a starting point \(S_j\), a goal \(G_j\) and a time limit \(T_j\) seconds.

The rules of the marathon are as follows:

• The participant starts at \(S_j\).
• The participant must pick up all \(N\) balls. Picking up a ball takes 1 second regardless of how many balls have already been collected.
• When running while carrying \(x\) balls, running 1 meter takes \(x+1\) seconds.
• The participant must finish at \(G_j\) within \(T_j\) seconds to be considered to have completed the marathon.

Your task is to determine for each proposal whether it is possible to complete the marathon within the designated time limit, assuming an optimal strategy of collecting the balls.

Note: All formulas are represented in \(\LaTeX\) format.

inputFormat

The input is given as follows:

L N Q
X1 X2 ... XN
S1 G1 T1
S2 G2 T2
... (Q lines in total)

Here, \(L\) (the road length), \(N\) (the number of balls) and \(Q\) (the number of proposals) are integers. The next line contains \(N\) integers \(X_i\) specifying the locations of the balls. Each of the following \(Q\) lines contains three integers \(S_j\), \(G_j\) and \(T_j\) representing a proposal.

outputFormat

For each proposal, output a line containing YES if it is possible to finish the marathon within the given time limit, or NO otherwise.

sample

20 3 3
5 10 15
0 20 53
20 0 53
10 10 33

YES
YES
YES