AT_abc467_g [ABC467G] Many Sweets Problem

There is a length- $ N $ sequence of positive integers $ A=(A_1,A_2,\dots,A_N) $ . Process the following query $ Q $ times. - `c x l r k` : Update the value of $ A_c $ to $ x $ . Then, solve the following sub-problem and output the answer. > There are $ r-l+1 $ sweets. The deliciousness of the $ i $ -th sweet is $ A_{l+i-1} $ . > You decide to eat sweets until the total deliciousness of the sweets eaten becomes $ k $ or more. > What is the minimum possible number of sweets you eat, if you optimally choose which sweets to eat? Output the answer. > If the total deliciousness cannot become $ k $ or more no matter how you choose the sweets to eat, output $ -1 $ instead.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query $ \mathrm{query}_q $ is given in the following format: > $ c $ $ x $ $ l $ $ r $ $ k $

Output $ Q $ lines. The $ q $ -th line should contain the answer to the $ q $ -th query.

### Sample Explanation 1 We explain the first query. First, update $ A_1 $ to $ 1 $ . Then, $ A=(1,2,4,1,7,3,6) $ . Now, solve the sub-problem. In the sub-problem, there are four sweets, with deliciousness $ 1,7,3,6 $ in order. To minimize the number of sweets eaten so that the total deliciousness becomes $ k=9 $ or more, it is optimal to eat the second and fourth sweets. Thus, the answer to the sub-problem is $ 2 $ . ### Constraints - $ 1 \leq N \leq 10^5 $ - $ 1 \leq Q \leq 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - $ 1 \leq c \leq N $ - $ 1 \leq x \leq 10^9 $ - $ 1 \leq l \leq r \leq N $ - $ 1 \leq k \leq 10^{15} $ - All input values are integers.