AT_aalc001_c セグメント木上の二分探索

長さ $ N $ の非負整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 クエリを $ Q $ 個処理してください。クエリは以下の $ 3 $ 種類のいずれかです。 - `1 i x`： $ A_i $ を $ x $ に変更する。 - `2 l t`： $ \displaystyle \sum_{i=l}^{r} A_i \geq t $ を満たす $ l $ 以上 $ N $ 以下の整数 $ r $ のうち、最小のものを出力する。そのような整数 $ r $ が存在しない場合は、 $ N+1 $ を出力する。 - `3 r t`： $ \displaystyle \sum_{i=l}^{r} A_i \geq t $ を満たす $ 1 $ 以上 $ r $ 以下の整数 $ l $ のうち、最大のものを出力する。そのような整数 $ l $ が存在しない場合は、 $ 0 $ を出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下のいずれかの形式で与えられる。 > $ 1 $ $ i $ $ x $ > $ 2 $ $ l $ $ t $ > $ 3 $ $ r $ $ t $

$ 2 $ 種類目または $ 3 $ 種類目のクエリを合わせた個数を $ q $ として、 $ q $ 行出力せよ。 $ j $ 行目には、 $ 2 $ 種類目または $ 3 $ 種類目のクエリのうち $ j $ 番目のものに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリでは、 $ A_2=1 \lt 4 $ である一方、 $ A_2+A_3=4 $ であるため、 $ 3 $ を出力します。 $ 2 $ 番目のクエリでは、 $ A_3+A_4+A_5=7 $ である一方、 $ A_4+A_5=4 $ であるため、 $ 3 $ を出力します。 $ 3 $ 番目のクエリでは、 $ A $ は $ (2,1,1,0,4) $ に変更されます。 $ 4 $ 番目のクエリでは、 $ A_2+A_3+A_4=2 \lt 4 $ である一方、 $ A_2+A_3+A_4+A_5=6 $ であるため、 $ 5 $ を出力します。 $ 5 $ 番目のクエリでは、 $ A_4+A_5=4 \lt 5 $ である一方、 $ A_3+A_4+A_5=5 $ であるため、 $ 3 $ を出力します。 $ 6 $ 番目のクエリでは、 $ A_4+A_5=4 \lt 5 $ であり、条件を満たす $ r $ は存在しないため、 $ 6 $ を出力します。 $ 7 $ 番目のクエリでは、 $ A_1+A_2=3 \lt 4 $ であり、条件を満たす $ l $ は存在しないため、 $ 0 $ を出力します。 $ 8 $ 番目のクエリでは、 $ A_1=2 $ であるため、 $ 1 $ を出力します。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq A_i \leq 10^9 $ - $ 1 $ 種類目のクエリについて、 $ 1 \leq i \leq N $ , $ 0 \leq x \leq 10^9 $ - $ 2 $ 種類目のクエリについて、 $ 1 \leq l \leq N $ , $ 1 \leq t \leq 10^{15} $ - $ 3 $ 種類目のクエリについて、 $ 1 \leq r \leq N $ , $ 1 \leq t \leq 10^{15} $ - 入力される数値はすべて整数