Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

\(N\) pénzérmét sorba raktunk. Minden pénzérme egyik oldalán \(0\) a másik oldalán \(1\) áll. A pénzérméknek csak egyik oldala látható. Az \(S\) string a pénzérmék látható oldalát ábrázolja, a sorozat első érméjétől az utolsóig leolvasva. Ezen a sorozaton el kell végezni \(Q\) változtatást. Az \(i\)-edig változtatást két számmal, az \(L_i\) és \(R_i\) számokkal írjuk le. E két szám azt jelenti, hogy az összes pénzérmét megfordítjuk az \(L_i\)-től \(R_i\)-ig terjedő részsorozatban.

Például, ha \(S=0101101\), \(L_1=2\) és \(R_1=6\), az első változtatás után \(S=0010011\).

Minden változtatás után kiíratni a legkisebb árat ahhoz, hogy az összes pénzérmét úgy fordítsuk meg, hogy azok látható oldalán 0 legyen. Ehhez a következő két operációt alkalmazhatjuk akárhányszor, tetszőleges sorrendben:

Ügyeljetek arra, a sorozaton csak \(Q\) számú adott változtatást hajtunk végre. Azokat az operációkat, amellyel minden pénzérmét úgy fordítanánk meg, hogy \(0\) legyen a látható oldalukon, nem végezzük el a pénzérme sorozaton, csak azok teljes árát kell megtalálni.

Bemenet

A bemenet első sorában 3 egész szám \(N\), \(C\) és \(Q\) áll. A következő sorban az \(S\) string áll. A következő \(Q\) sor mindegyikében 2 egész szám \(L_i\) és \(R_i\) áll.

Kimenet

A kimenetre kiíratni \(Q\) sort. Az \(i\)-edik sorban a keresett legkisebb ár legyen az \(i\)-edik változtatás után.

Korlátozások

A tesztpéldák 9 független csoportba oszthatók:

Példák

1. példa

Bemenet

7 2 3
0111011
1 2
1 2
2 6

Kimenet

4
3
2

Magyarázat

2. példa

Bemenet

16 3 5
0111001111011001
16 16
1 1
3 3
5 5
7 7

Kimenet

6
6
7
6
7