Problem Description

Snuke is about to submit a bit string \( S \) of length \( N \) to a review committee. Here, a bit string is a string consisting only of 0 and 1.

There are \( M \) review criteria, and the \( i \)-th criterion (\( 1 \leq i \leq M \)) is as follows:

• The substring of \( S \) from the \( L_i \)-th to the \( R_i \)-th character contains at least one 1.

The number of criteria that the bit string satisfies is its score.

Smeke, Snuke's rival, decided to modify Snuke's bit string \( S \) \( Q \) times. In the \( j \)-th modification (\( 1 \leq j \leq Q \)), the \( X_j \)-th character from the beginning will be flipped: if it is 0, it becomes 1, and if it is 1, it becomes 0.

Your task is to calculate the score of the bit string after each of the \( Q \) modifications on Smeke's behalf.

Input Format

The input is given from the standard input in the following format:

\( N \) \( M \) \( Q \) \( S \) \( L_1 \) \( R_1 \) : \( L_M \) \( R_M \) \( X_1 \) : \( X_Q \)

Output Format

Output \( Q \) lines. The \( i \)-th line should contain the score of the bit string after applying the first \( i \) modifications.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4
0
2
3

Sample Input #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

Sample Output #2

8
8
7
7
7
7
5
7
7
5

Notes/Hints

Constraints

• \( 1 \leq N \leq 2 \times 10^5 \)
• \( 1 \leq M \leq 10^5 \)
• \( 1 \leq Q \leq 2 \times 10^5 \)
• \( S \) is a string of length \( N \) consisting of 0 and 1
• \( 1 \leq L_i \leq R_i \leq N \)
• \( 1 \leq X_j \leq N \)
• All inputs except \( S \) are integers

Sample Explanation 1

• After the first query, the bit string becomes 010, which satisfies all criteria.
• After the second query, the bit string becomes 000, which satisfies none of the criteria.
• After the third query, the bit string becomes 100, which satisfies the 1st and 3rd criteria.
• After the fourth query, the bit string becomes 101, which satisfies the 1st, 3rd, and 4th criteria.

见题面 Input 部分

见题面 Output 部分