AT_aalc001_q 移動回数

You are given positive integers $ N,M,Q $ , a string $ S $ of length $ N $ consisting of `0` and `1`, and a sequence of positive integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . Process $ Q $ queries. Each query is of one of the following $ 2 $ types: - `1 i`: Change the $ i $ -th character $ S_i $ of $ S $ from `0` to `1`, or from `1` to `0`. - `2 x l r`: Find the amount of money obtained by the following procedure: - You start at coordinate $ x $ on a number line with $ 0 $ yen. - For $ i=l,l+1,\ldots,r $ in this order, do the following: - Face in the negative direction if $ S_i $ is `0`, and in the positive direction if it is `1`. - Repeat the following operation $ A_i $ times: - If the coordinate $ 1 $ unit ahead in the direction you are facing is between $ 0 $ and $ M $ , inclusive, move there and receive $ 1 $ yen. Otherwise, keep your position and the amount of money unchanged. For each type $ 2 $ query, start the procedure at the specified coordinate $ x $ with $ 0 $ yen, without carrying over your movement or money from other queries.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ Q $ $ S $ $ 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 $ > $ 2 $ $ x $ $ l $ $ r $

Let $ q $ be the number of type $ 2 $ queries. Print $ q $ lines. The $ j $ -th line should contain the amount of money you have at the end of the procedure for the $ j $ -th type $ 2 $ query.

### Sample Explanation 1 For query $ 1 $ , starting at coordinate $ 5 $ , you attempt to move in the positive, negative, positive, negative, and negative directions in this order. Your coordinates after the respective stages are $ 9,1,4,0,0 $ , and you receive $ 19 $ yen. For query $ 3 $ , starting at coordinate $ 5 $ , you attempt to move in the positive, positive, positive, negative, and negative directions in this order. Your coordinates after the respective stages are $ 9,10,10,4,2 $ , and the amount of money obtained is $ 13 $ yen. ### Constraints - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le M \le 10^9 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ S $ is a string of length $ N $ consisting of `0` and `1`. - $ 1 \le A_i \le 10^9 $ - For type $ 1 $ queries, $ 1 \le i \le N $ - For type $ 2 $ queries, $ 0 \le x \le M $ , $ 1 \le l \le r \le N $ - All numerical values in the input are integers.