AT_aalc001_q 移動回数

正整数 $ N,M,Q $ と、`0` と `1` からなる長さ $ N $ の文字列 $ S $ と、長さ $ N $ の正整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 クエリを $ Q $ 個処理してください。クエリは以下の $ 2 $ 種類のいずれかです。 - `1 i`： $ S $ の $ i $ 文字目 $ S_i $ を、`0` ならば `1` に、`1` ならば `0` に変更する。 - `2 x l r`：次の手順で得られる金額を求める。 - あなたは数直線上の座標 $ x $ にいて、所持金は $ 0 $ 円である。 - $ i=l,l+1,\ldots,r $ の順に、以下を行う。 - $ S_i $ が `0` ならば負の向きを、`1` ならば正の向きを向く。 - 次の操作を $ A_i $ 回繰り返す。 - 向いている方向へ $ 1 $ 進んだ先の座標が $ 0 $ 以上 $ M $ 以下ならば、そこへ進んで $ 1 $ 円を得る。そうでなければ、位置と所持金を変化させない。 $ 2 $ 種類目の各クエリでは、ほかのクエリでの移動や所持金を引き継がず、指定された座標 $ x $ と所持金 $ 0 $ 円から手順を開始します。

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

$ 2 $ 種類目のクエリの個数を $ q $ として、 $ q $ 行出力せよ。 $ j $ 行目には、 $ j $ 番目の $ 2 $ 種類目のクエリに対する答えとして、手順を終えた時点での所持金を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリでは、座標 $ 5 $ から順に正、負、正、負、負の向きへ進もうとします。各段階を終えた時点の座標は順に $ 9,1,4,0,0 $ であり、 $ 19 $ 円を得ます。 $ 3 $ 番目のクエリでは、座標 $ 5 $ から順に正、正、正、負、負の向きへ進もうとします。各段階を終えた時点の座標は順に $ 9,10,10,4,2 $ であり、得られる金額は $ 13 $ 円になります。 ### Constraints - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le M \le 10^9 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ S $ は `0` と `1` からなる長さ $ N $ の文字列 - $ 1 \le A_i \le 10^9 $ - $ 1 $ 種類目のクエリについて、 $ 1 \le i \le N $ - $ 2 $ 種類目のクエリについて、 $ 0 \le x \le M $ , $ 1 \le l \le r \le N $ - 入力される数値はすべて整数