Cho một dãy $a$ gồm $n$ phần tử. Bạn phải thực hiện $q$ truy vấn, mỗi truy vấn yêu cầu bạn phải tìm số $r$ lớn nhất sao cho $r \le n$ và $(\Sigma^{i \le r}_{i = l}(a_i \times [u \le a_i \le v])) \le k$. Trong đó:

• $\Sigma^{i \le r}_{i = l} c_i$ là tổng các giá trị $c_i$ mọi trường hợp $i$ từ $l$ đến $r$.
• $[u \le a_i \le v]$ là hàm chân lý, trả về $1$ (true) khi và chỉ khi $u \le a_i \le v$ và trả về $0$ (false) trong các trường hợp còn lại.

Hay nói cách khác, bạn cần tìm giá trị $r$ lớn nhất sao cho đoạn mã giả sau trả về một giá trị $s \le k$ (lưu ý: $r$ có thể bằng $l - 1$):

gán s bằng 0

với mọi i từ l đến r:
    nếu u <= a_i <= v:
        tăng s lên a_i

trả về s

7 3
4 6 8 2 10 5 1
4 1 5 7
1 2 3 5
1 1 10 15

6
7
2