쇼핑

어느 할인 매장의 진열대에 상품 n개가 한 줄로 놓여 있다. 왼쪽에서 i번째 상품의 개당 가격은 $a_i$ 달러이고, 상품마다 재고는 무제한이다.

손님 q명이 차례로 매장에 들어온다. i번째 손님은 $v_i$ 달러를 가지고 $l_i$번째 상품에서 출발해 오른쪽으로 한 칸씩 이동하며 $r_i$번째 상품까지 살펴본다.

손님은 상품을 하나 볼 때마다 남은 돈으로 살 수 있는 최대 개수만큼 그 상품을 산다. 개당 가격이 남은 돈보다 비싼 상품은 사지 않고 지나간다.

손님마다 다 살펴본 뒤에 남은 돈이 얼마인지 구하라.

첫째 줄에 상품의 개수 n과 손님의 수 q가 공백으로 구분되어 주어진다. ($1 \le n, q \le 200000$)

둘째 줄에 상품의 가격 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 10^{18}$)

다음 q개의 줄에는 손님 한 명의 정보가 한 줄씩 $v_i$, $l_i$, $r_i$ 순서로 공백으로 구분되어 주어진다. ($1 \le v_i \le 10^{18}$, $1 \le l_i \le r_i \le n$)

q개의 줄에 걸쳐, 각 손님이 다 살펴본 뒤에 남은 돈을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.