Shopping

A discount store keeps n products in a row on one shelf. The ith product from the left costs $a_i$ dollars per unit, and every product has unlimited stock.

q customers walk in one after another. Customer i carries $v_i$ dollars, starts at product $l_i$, and moves one step to the right at a time until product $r_i$ has been looked at.

Every time a customer looks at a product, that customer buys as many units of it as the remaining money allows. A product whose unit price is higher than the remaining money is skipped.

For each customer, find how much money is left after the last product has been looked at.

The first line contains the number of products n and the number of customers q, separated by a space. ($1 \le n, q \le 200000$)

The second line contains the prices $a_1, a_2, \dots, a_n$, separated by spaces. ($1 \le a_i \le 10^{18}$)

Each of the next q lines describes one customer with three integers $v_i$, $l_i$, $r_i$, separated by spaces. ($1 \le v_i \le 10^{18}$, $1 \le l_i \le r_i \le n$)

Print q lines. On the ith line, print the money customer i has left after the last product has been looked at, in the order the customers are given in the input.