\(N\) новчића поређано је у низ. Сваки новчић има број \(0\) написан на једној страни и број \(1\) на другој. Тачно једна страна сваког новчића је видљива. Стринг \(S\) представља видљиве цифре новчића прочитане од почетка до краја низа. Над овим низом новчића треба извршити \(Q\) промена, где је \(i\)-та промена описана са два броја \(L_i\) и \(R_i\), што значи да је потребно окренути све новчиће на поднизу од \(L_i\) до \(R_i\).

На пример ако је \(S=0101101\), \(L_1=2\) и \(R_1=6\) после прве промене \(S=0010011\).

После сваке промене исписати најмању могућу укупну цену да се сви новчићи окрену тако да им је број 0 на видљивој страни, ако је могуће примењивати следеће две операције призвољан број пута у произвољном редоследу: - Окрени један новчић за цену \(1\). - Окрени све новчиће на неком поднизу узастопних новчића за цену \(C\).

Обратите пажњу на то да се само \(Q\) задатих промена заправо примењује на низ, док се операције којима бисмо окренули све новчиће тако да им је \(0\) на видљивој страни, не примењују на низ новчића, већ је само потребно наћи њихову најмању могућу укупну цену.

Опис улаза

У првом реду улаза налазе се 3 цела броја \(N\), \(C\) и \(Q\). У следећем реду налази се стринг \(S\). У наредних \(Q\) редова налазе се по 2 цела броја \(L_i\) и \(R_i\).

Опис излаза

На излаз испишите \(Q\) редова, у \(i\)-том реду тражену најмању цену после \(i\)-те промене.

Ограничења

• \(1 \leq C \leq N \leq 2 \times 10^5\)
• \(1 \leq Q \leq 2 \times 10^5\)
• \(1 \leq L_i \leq R_i \leq N\)
• \(|S|=N\)
• Стринг \(S\) се састоји само од цифара \(0\) и \(1\).

Тест примери су подељени у 9 дисјунктних група:

• У тест примерима вредним \(2\) поена: \(N, Q \leq 4000\), \(C=N\)
• У тест примерима вредним \(2\) поена: \(L_i=R_i\) за свако \(i\), \(C=N\)
• У тест примерима вредним \(12\) поена: \(C=N\)
• У тест примерима вредним \(4\) поена: \(N, Q \leq 4000\), \(C=1\)
• У тест примерима вредним \(6\) поена: \(C=1\)
• У тест примерима вредним \(8\) поена: \(N \leq 1000\), \(Q=1\)
• У тест примерима вредним \(18\) поена: \(Q=1\)
• У тест примерима вредним \(20\) поена: \(L_i=R_i\) за свако \(i\)
• У тест примерима вредним \(28\) поена: нема додатних ограничења

Примери

Пример 1

Улаз

7 2 3
0111011
1 2
1 2
2 6

Излаз

4
3
2

Објашњење

• После прве помене \(S=1011011\) и оптимално је окренути цео низ новчића за цену \(2\) и затим окренути други и пети новчић. Укупна цена је \(2+1*2=4\).
• После друге промене \(S=0111011\) и оптимално је окренути новчиће од другог до последњег за цену \(2\) и затим окренути пети новчић. Укупна цена је \(2+1=3\).
• После треће промене \(S=0000101\) и оптимално је окренути пети и седми новчић. Укупна цена је \(1+1=2\).

Пример 2

Улаз

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

Излаз

6
6
7
6
7