AT_abc467_g [ABC467G] Many Sweets Problem

長さ $ 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 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

$ Q $ 行出力せよ。 $ q $ 行目には $ q $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリについて説明します。 まず、 $ A_1 $ を $ 1 $ に更新します。 $ A=(1,2,4,1,7,3,6) $ になります。そして小問題を解きます。 小問題ではお菓子は $ 4 $ 個あり、美味しさは順に $ 1,7,3,6 $ です。 食べたお菓子の美味しさの総和が $ k=9 $ 以上になるように食べるお菓子の個数を最小化するには、 $ 2 $ 番目のお菓子と $ 4 $ 番目のお菓子を食べるのが最適です。よって小問題の答えは $ 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} $ - 入力される値は全て整数