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

You are given a sequence of nonnegative integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . Process $ Q $ queries. Each query is of one of the following $ 3 $ types: - `1 i x`: Change $ A_i $ to $ x $ . - `2 l t`: Print the smallest integer $ r $ between $ l $ and $ N $ , inclusive, that satisfies $ \displaystyle \sum_{i=l}^{r} A_i \geq t $ . If no such integer $ r $ exists, print $ N+1 $ . - `3 r t`: Print the largest integer $ l $ between $ 1 $ and $ r $ , inclusive, that satisfies $ \displaystyle \sum_{i=l}^{r} A_i \geq t $ . If no such integer $ l $ exists, print $ 0 $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in one of the following formats: > $ 1 $ $ i $ $ x $ > $ 2 $ $ l $ $ t $ > $ 3 $ $ r $ $ t $

Let $ q $ be the total number of queries of types $ 2 $ and $ 3 $ . Print $ q $ lines. The $ j $ -th line should contain the answer to the $ j $ -th query among those of types $ 2 $ and $ 3 $ , in the order they are given.

### Sample Explanation 1 For query $ 1 $ , $ A_2=1 \lt 4 $ while $ A_2+A_3=4 $ , so print $ 3 $ . For query $ 2 $ , $ A_3+A_4+A_5=7 $ while $ A_4+A_5=4 $ , so print $ 3 $ . Query $ 3 $ changes $ A $ to $ (2,1,1,0,4) $ . For query $ 4 $ , $ A_2+A_3+A_4=2 \lt 4 $ while $ A_2+A_3+A_4+A_5=6 $ , so print $ 5 $ . For query $ 5 $ , $ A_4+A_5=4 \lt 5 $ while $ A_3+A_4+A_5=5 $ , so print $ 3 $ . For query $ 6 $ , $ A_4+A_5=4 \lt 5 $ , and no $ r $ satisfies the condition, so print $ 6 $ . For query $ 7 $ , $ A_1+A_2=3 \lt 4 $ , and no $ l $ satisfies the condition, so print $ 0 $ . For query $ 8 $ , $ A_1=2 $ , so print $ 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 $ - For type $ 1 $ queries, $ 1 \leq i \leq N $ , $ 0 \leq x \leq 10^9 $ - For type $ 2 $ queries, $ 1 \leq l \leq N $ , $ 1 \leq t \leq 10^{15} $ - For type $ 3 $ queries, $ 1 \leq r \leq N $ , $ 1 \leq t \leq 10^{15} $ - All numerical values in the input are integers.