AT_nikkei2019_2_final_e Notorious B.I.T.

[problemUrl]: https://atcoder.jp/contests/nikkei2019-2-final/tasks/nikkei2019_2_final_e すぬけ君は長さ $ N $ のビット列 $ S $ を審査会に提出しようとしています。ここで、ビット列とは `0` と `1` のみからなる文字列を意味します。 審査基準は $ M $ 個あり、$ i\ (1\ \leq\ i\ \leq\ M) $ 番目の審査基準は以下の通りです。 - $ S $ の $ L_i $ 文字目から $ R_i $ 文字目までを切り出した部分文字列のうちに `1` が含まれる。 ビット列が満たす審査基準の個数が、そのビット列に対するスコアとなります。 すぬけ君のライバルであるスメケ君は、すぬけ君の提出するビット列 $ S $ を $ Q $ 回変更することにしました。$ j\ (1\ \leq\ j\ \leq\ Q) $ 回目の変更では先頭から $ X_j $ 文字目を、`0` ならば `1` に、`1` ならば `0` に変更します。 あなたの仕事はスメケ君の代わりに、$ Q $ 回ある変更それぞれの後にできるビット列のスコアを求めることです。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ Q $ $ S $ $ L_1 $ $ R_1 $ : $ L_M $ $ R_M $ $ X_1 $ : $ X_Q $

$ Q $ 行出力してください。$ i $ 行目には、$ i $ 番目までの変更を施してできるビット列のスコアを出力してください。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ S $ は `0`, `1` からなる長さ $ N $ の文字列である - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - $ 1\ \leq\ X_j\ \leq\ N $ - $ S $ 以外の入力はすべて整数である ### Sample Explanation 1 \- $ 1 $ つ目のクエリの後、ビット列は `010` になり、これは全ての審査条件を満たします。 - $ 2 $ つ目のクエリの後、ビット列は `000` になり、これはどの審査条件も満たしません。 - $ 3 $ つ目のクエリの後、ビット列は `100` になり、これは $ 1,\ 3 $ 番目の審査条件を満たします。 - $ 4 $ つ目のクエリの後、ビット列は `101` になり、これは $ 1,\ 3,\ 4 $ 番目の審査条件を満たします。