Una \((R, B)\)-secuencia es la secuencia formada por \(R\) letras R seguidas de \(B\) letras B.

Se tiene un texto \(S\) con las letras R, B y G, y \(W\) consultas. Cada consulta indica un tramo contiguo \(S_L S_{L+1} \dots S_U\), y pregunta la mínima cantidad de operaciones para transformar ese tramo en la \((R, B)\)-secuencia. Una operación es agregar, quitar o reemplazar una letra en cualquier posición (es decir, se pide la distancia de edición entre el tramo y la \((R,B)\)-secuencia).

Las consultas no modifican \(S\).

Entrada

La primera línea tiene dos enteros \(R\) y \(B\) \((1 \le R, B \le 10^6)\).

La segunda línea tiene el texto \(S\) \((1 \le |S| \le 5 \cdot 10^5)\), con caracteres R, B o G.

La tercera línea tiene un entero \(W\) \((1 \le W \le 10^5)\).

Cada una de las siguientes \(W\) líneas tiene dos enteros \(L\) y \(U\) \((1 \le L \le U \le |S|)\).

Salida

Para cada consulta, en orden, una línea con la mínima cantidad de operaciones.

Notas

Con \(R = 3\) y \(B = 2\), el tramo BGR necesita \(4\) operaciones: reemplazar las dos primeras letras por R y agregar dos B al final.

Ejemplo 1

Entrada

3 2
RRBGRB
3
3 5
1 5
1 3

Salida

4
3
2

Ejemplo 2

Entrada

2 3
RRGRBR
6
1 3
1 2
1 4
3 3
3 5
5 6

Salida

3
3
3
5
3
4

Ejemplo 3

Entrada

5 6
GRBBBB
4
4 5
1 4
5 6
2 2

Salida

9
8
9
10

Ejemplo 4

Entrada

1 1
RB
2
1 1
1 2

Salida

1
0

Regional Latinoamericana 2024 del ICPC, problema C («Cindy's Christmas Challenge»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.