ICPC PACNW 2016 J - Shopping - DMOJ: Modern Online Judge

ICPC PACNW 2016 J - Shopping

Points: 15

Time limit: 2.5s

Memory limit: 256M

Problem type

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

There are $q$ $q$ customers who will enter the store to buy items. The $i$ $i$ th customer has $v_i$ $v_{i}$ dollars, starts at item $l_i$ $l_{i}$ and walks to the right to item $r_i$ $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$ $n$ and $q$ $q$ $(1 \le n, q \le 200\,000)$ $(1 \leq n, q \leq 200 000)$ .

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

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

Output

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

Sample Input

Copy

Sample Output

Copy

2
0
1

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

1

Jinx commented on Oct. 14, 2023, 9:43 p.m.

nice of yall to make the very last case time out and not even give partial points 💀