ICPC PACNW 2016 J - Shopping

View as PDF

Submit solution

Points: 15
Time limit: 2.5s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Java, Python

The sale bin of Big Box Bargains contains n products in a row. The ith item has price a_i per unit. There is no limit to the quantity of any item.

There are q customers who will enter the store to buy items. The ith customer has v_i dollars, starts at item l_i and walks to the right to item r_i (inclusive), one item at a time.

Each time they encounter an item, they will buy as many units of the item as they can afford.

You are now wondering, for each customer, how much money they will have left after buying items.

Input

The first line of input contains two space-separated integers n and q (1 \le n, q \le 200\,000).

The next line of input contains n space-separated integers a_i (1 \le a_i \le 10^{18}).

Each of the next q lines contains three space-separated integers v_i (1 \le v_i \le 10^{18}), l_i, and r_i (1 \le l_i \le r_i \le n).

Output

For each of the q customers, print, on a single line, a single integer indicating the remaining amount of money after shopping.

Sample Input

5 3
5 3 2 4 6
8 5 5
107 1 4
7 3 5

Sample Output

2
0
1
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.