D. Профессор Хигасиката
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джосуке устал от спокойной жизни в Мориохе. Пойдя по стопам своего племянника Дзётаро, он решает упорно учиться и стать профессором информатики. Просматривая в Интернете задачи по программированию, он наткнулся на следующую.

Пусть $$$s$$$ — бинарная строка длины $$$n$$$. Операция над $$$s$$$ определяется как выбор двух различных целых чисел $$$i$$$ и $$$j$$$ ($$$1 \leq i < j \leq n$$$), и обмен местами символов $$$s_i, s_j$$$.

Рассмотрим $$$m$$$ строк $$$t_1, t_2, \ldots, t_m$$$, где $$$t_i$$$ — подстрока$$$^\dagger$$$ из $$$s$$$ от $$$l_i$$$ до $$$r_i$$$. Определим $$$t(s) = t_1+t_2+\ldots+t_m$$$ как конкатенацию строк $$$t_i$$$ в таком порядке.

Существует $$$q$$$ обновлений строки. В $$$i$$$-м обновлении $$$s_{x_i}$$$ инвертируется. То есть, если $$$s_{x_i}=1$$$, то $$$s_{x_i}$$$ становится $$$0$$$ и наоборот. После каждого обновления найдите минимальное количество операций, которые нужно выполнить над $$$s$$$, чтобы сделать $$$t(s)$$$ лексикографически как можно большим$$$^\ddagger$$$.

Обратите внимание, что на самом деле ни одна операция не применяется. Нужно найти только количество операций.

Помогите Йосуке в его мечте, решив за него эту задачу.

——————————————————————

$$$\dagger$$$ Строка $$$a$$$ является подстрокой строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, нуля или всех) символов из начала и нескольких (возможно, нуля или всех) символов из конца.

$$$\ddagger$$$ Строка $$$a$$$ лексикографически больше строки $$$b$$$ такой же длины тогда и только тогда, когда выполняется следующее условие:

  • в первой позиции, где $$$a$$$ и $$$b$$$ отличаются, в строка $$$a$$$ стоит $$$1$$$, а в строке $$$b$$$ стоит $$$0$$$.
Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n,m,q \leq 2 \cdot 10^5$$$).

Вторая строка содержит бинарную строку $$$s$$$ длины $$$n$$$, состоящую только из цифр $$$0$$$ и $$$1$$$.

В $$$i$$$-й среди следующих $$$m$$$ строк содержатся два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$).

В $$$i$$$-й среди следующих $$$q$$$ строк содержится одно целое число $$$x_i$$$ ($$$1 \leq x_i \leq n$$$).

Выходные данные

Выведите $$$q$$$ целых чисел. В строке $$$i$$$ выведите минимальное количество операций, которое необходимо выполнить над $$$s$$$, чтобы получить лексикографически наибольшую возможную строку $$$t(s)$$$ после $$$i$$$-го обновления.

Примеры
Входные данные
2 2 4
01
1 2
1 2
1
1
2
2
Выходные данные
0
1
0
1
Входные данные
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
Выходные данные
2
3
2
2
1
2
2
2
2
2
Примечание

В первом примере:

Изначально $$$t(s) = s(1,2) + s(1,2) = 0101$$$.

После $$$1$$$-го запроса, $$$s$$$ становится $$$11$$$ и, соответственно, $$$t$$$ становится $$$1111$$$. Никаких операций выполнять не нужно, так как $$$t(s)$$$ уже является лексикографически наибольшей строкой из возможных.

После $$$2$$$-го запроса $$$s$$$ становится $$$01$$$ и, следовательно, $$$t$$$ становится $$$0101$$$. Необходимо выполнить операцию $$$1$$$, поменяв местами $$$s_1$$$ и $$$s_2$$$. Следовательно, $$$t(s)$$$ становится $$$1010$$$, что является лексикографически наибольшей строкой, которую можно получить.