Yard Sale

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M
Java 128M
PyPy 2 128M
PyPy 3 128M

Problem type

Over the weekend, Bob is going to a yard sale hosted by one of his neighbors. When he arrives, he notices that there is a long table that has N items arranged on it in a row. Bob estimates the value of the items in dollars as a_1, a_2, ..., a_N in order.

To get rid of as many items as possible, Bob's neighbor sells in a very particular way. He will make Bob Q offers to sell all the items in the range [L_i, R_i] for a price of P_i dollars.

In order to maximize his profits, Bob has asked you to tell him which of the Q offers are profitable for him. For an offer to be profitable, the sum of the values in the range must be strictly greater than the price offered.

Input Specification

The first line of input will contain two space-separated integers, N (1 \le N \le 2 \cdot 10^5) and Q (1 \le Q \le 10^5).

The next line of input will contain N space-separated integers, a_1, a_2, ..., a_N (1 \le a_i \le 1000).

The next Q lines of input will each contain three space-separated integers, L_i, R_i (1 \le L_i \le R_i \le N), and P_i (1 \le P_i \le 10^9).

Output Specification

For each query, output on a new line good if the offer is profitable for Bob and bad if it's not.


Subtask 1 [20%]

1 \le N, Q \le 100

Subtask 2 [80%]

No further constraints.

Sample Input

3 3
5 1 6
1 2 3
1 3 13
2 3 7

Sample Output


Explanation for Sample Output

For the first offer, the total value is 5 + 1 = 6 dollars so Bob earns a profit if he pays 3 dollars.

For the second offer, the total value is 5 + 1 + 6 = 12 dollars so Bob loses money if he pays 13 dollars.

For the third offer, the total value is 1 + 6 = 7 dollars so Bob does not earn a profit if he pays 7 dollars.


There are no comments at the moment.