問題文

すぬけ君は長さ 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 回ある変更それぞれの後にできるビット列のスコアを求めることです。

制約

• 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 以外の入力はすべて整数である

入力例 1

3 4 4
011
1 3
2 2
1 2
2 3
3
2
1
3

出力例 1

4
0
2
3

• 1 つ目のクエリの後、ビット列は 010 になり、これは全ての審査条件を満たします。
• 2 つ目のクエリの後、ビット列は 000 になり、これはどの審査条件も満たしません。
• 3 つ目のクエリの後、ビット列は 100 になり、これは 1, 3 番目の審査条件を満たします。
• 4 つ目のクエリの後、ビット列は 101 になり、これは 1, 3, 4 番目の審査条件を満たします。

入力例 2

50 10 10
10010000000001000000001000000000000000000100000000
2 25
11 33
20 31
21 26
26 50
4 42
23 40
2 8
36 37
15 18
20
1
4
49
14
10
23
37
42
20

出力例 2

8
8
7
7
7
7
5
7
7
5