AT_abc467_g.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.

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。你需要处理 $Q$ 个查询。

• c x l r k：将 $A_c$ 的值更新为 $x$。然后，求解如下子问题并输出答案。

共有 $r-l+1$ 颗糖果。第 $i$ 颗糖果的美味值为 $A_{l+i-1}$。
你决定持续吃糖果，直到所吃糖果的总美味值达到或超过 $k$。
若你能最优地选择要吃的糖果，则最少需要吃多少颗糖果？请输出该最小值。
若无论怎样选择糖果，总美味值都无法达到或超过 $k$，则输出 $-1$。

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$

输入从标准输入中按以下格式给出：

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询 $\mathrm{query}_q$ 的格式如下：

$c$ $x$ $l$ $r$ $k$

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

输出 $Q$ 行。第 $q$ 行应包含第 $q$ 个查询的答案。

Sample 1 Explanation:
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.

样例 1 解释：
我们解释第一个查询。
首先，将 $A_1$ 更新为 $1$。此时，$A=(1,2,4,1,7,3,6)$。接下来，求解该子问题。
在该子问题中，共有四颗糖果，其美味值依次为 $1,7,3,6$。
为使所吃糖果的总美味值达到 $k=9$ 或更高，且所吃糖果数量最少，最优策略是吃下第二颗和第四颗糖果。因此，该子问题的答案为 $2$。

约束条件

• $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}$
• 所有输入值均为整数。