Luke (perhaps Skywalker) is a passionate computer science student. He receives as homework the following task:
Given a sequence of ~N~ integers, determine if the subsequence from ~x~ to ~y~ inclusive is a Great Sequence. A Great Sequence is a sequence that whose sum is strictly greater than ~K~.
Luke thought this is too easy, so he has thought up a new challenge: he'd like to know if a subsequence is an Amazing Sequence. An Amazing Sequence is a Great Sequence in which the integers ~a~ and ~b~ appear. Given his original sequence, he'd like to answer ~Q~ queries, determining if a subsequence is an Amazing Sequence.
For all subtasks, ~-10^9 \le K \le 10^9~ and ~-1\,000 \le a_i, b_i \le 1\,000~ and ~1 \le x_i \le y_i \le N~.
Subtask 1 [30%]
~N \le 1\,000~
~Q \le 1\,000~
Subtask 2 [70%]
~2 \le N \le 10^5~
~1 \le Q \le 10^5~
The first line of input will contain the space-separated integers ~N~, ~K~ and ~Q~. The second line of input will contain ~N~ space-separated integers representing the sequence. For the last ~Q~ lines, line ~i~ will contain query ~i~ in the format ~a_i~, ~b_i~, ~x_i~ and ~y_i~.
For each query, print
Yes if the subsequence is an Amazing Sequence,
5 6 3 1 3 4 5 6 3 6 2 5 1 4 1 4 5 6 1 3
Yes Yes No