D. Professor Higashikatatime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputJosuke is tired of his peaceful life in Morioh. Following in his nephew Jotaro's footsteps, he decides to study hard and become a professor of computer science. While looking up competitive programming problems online, he comes across the following one: Let s be a binary string of length n. An operation on s is defined as choosing two distinct integers i and j (1 \leq i < j \leq n), and swapping the characters s_i, s_j.Consider the m strings t_1, t_2, \ldots, t_m, where t_i is the substring ^\dagger of s from l_i to r_i. Define t(s) = t_1+t_2+\ldots+t_m as the concatenation of the strings t_i in that order.There are q updates to the string. In the i-th update s_{x_i} gets flipped. That is if s_{x_i}=1, then s_{x_i} becomes 0 and vice versa. After each update, find the minimum number of operations one must perform on s to make t(s) lexicographically as large^\ddagger as possible. Note that no operation is actually performed. We are only interested in the number of operations.Help Josuke in his dream by solving the problem for him. —————————————————————— \dagger A string a is a substring of a string b if a can be obtained from b by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.\ddagger A string a is lexicographically larger than a string b of the same length if and only if the following holds:   in the first position where a and b differ, the string a has a 1, and the string b has a 0. InputThe first line contains three integers n, m, q (1 \leq n,m,q \leq 2 \cdot 10^5). The next line contains a binary string s of length n, consisting only of digits 0 and 1.The i-th line of the next m lines contains two integers l_i and r_i (1 \leq l_i \leq r_i \leq n).The i-th line of the next q lines contains a single integer x_i (1 \leq x_i \leq n).OutputPrint q integers. The i-th integer is the minimum number of operations that need to be performed on s to get the lexicographically largest possible string t(s) in the i-th round.ExamplesInput
2 2 4
01
1 2
1 2
1
1
2
2
Output
0
1
0
1
Input
8 6 10
10011010
5 6
2 3
6 8
5 7
5 8
6 8
3
5
6
2
5
2
5
8
4
1
Output
2
3
2
2
1
2
2
2
2
2
NoteIn the first test case,Originally, t(s) = s(1,2) + s(1,2) = 0101.After the 1-st query, s becomes 11 and consequently t becomes 1111. You don't need to perform any operation as t(s) is already the lexicographically largest string possible.After the 2-nd query, s becomes 01 and consequently t becomes 0101. You need to perform 1 operation by swapping s_1 and s_2. Consequently, t(s) becomes 1010 which is the lexicographically largest string you can achieve.
2 2 4
01
1 2
1 2
1
1
2
2

0 1 0 1 
['data structures', 'dsu', 'greedy', 'implementation', 'strings', '*1900']