Monkeyland es una recta numérica infinita con $n$ monos, numerados del 1 al $n$. El $i$-ésimo mono se encuentra inicialmente en la posición $p[i]$ de la recta numérica. Es posible que varios monos compartan la misma posición inicial.
Pan puede hacer que cada mono se mueva con su hechizo encantador. La forma en que se mueve cada mono está determinada por una cadena $d$ de longitud $n$, donde cada carácter es L o R. Sea $d[i]$ el $i$-ésimo carácter de $d$.
Una vez lanzado el hechizo, el $i$-ésimo mono se mueve de la siguiente manera:
- Si $d[i] = \text{L}$, se mueve a la izquierda una posición.
- Si $d[i] = \text{R}$, se mueve a la derecha una posición.
Cada día, Pan lanzará su hechizo exactamente una vez. Si dos monos están en la misma posición en cualquier día (incluso inicialmente), se vuelven amigos. Si Pan lanzara su hechizo durante $k$ días, determine el número de pares de monos que se volverán amigos.
Entrada
Su programa debe leer desde la entrada estándar.
La primera línea de la entrada contiene dos enteros separados por espacios $n$ y $k$.
La segunda línea de la entrada contiene $n$ enteros separados por espacios $p[1], p[2], \dots, p[n]$.
La tercera línea de la entrada contiene una cadena $d$ de $n$ caracteres $d[1], d[2], \dots, d[n]$.
Salida
Su programa debe imprimir a la salida estándar.
Imprima un solo entero, el número de pares de monos que se volverán amigos.
La salida debe contener únicamente un solo entero. No imprima ningún texto adicional como Enter a number o The answer is.
Subtareas
Para todos los casos de prueba, la entrada satisfará los siguientes límites:
- $1 \le n \le 200\,000$
- $1 \le k \le 10^9$
- $1 \le p[i] \le 10^9$ para todo $1 \le i \le n$
- $d[i]$ es L o R para todo $1 \le i \le n$
Su programa será probado en instancias de entrada que satisfagan las siguientes restricciones:
| Subtarea | Puntuación | Restricciones adicionales |
|---|---|---|
| 0 | 0 | Casos de prueba de ejemplo |
| 1 | 6 | $n = 2$ |
| 2 | 13 | $d[1] = d[2] = \dots = d[n]$ |
| 3 | 10 | $n, k \le 200$ |
| 4 | 22 | $n, k \le 3000$ |
| 5 | 18 | $n \le 3000$ |
| 6 | 31 | Sin restricciones adicionales |
Ejemplos
Entrada 1
2 1 1 3 RL
Salida 1
1
Nota
Hay $n = 2$ monos y Pan lanza el hechizo por $k = 1$ día solamente. En el primer día, el mono 1 se mueve a la derecha de la posición 1 a la posición 2, mientras que el mono 2 se mueve a la izquierda de la posición 3 a la posición 2. Dado que terminan en la misma posición el primer día, se vuelven amigos. Por lo tanto, hay exactamente 1 par de monos que se vuelven amigos.
Entrada 2
5 67 1 2 3 4 5 RRRRR
Salida 2
0
Nota
Hay $n = 5$ monos y Pan lanza el hechizo por $k = 67$ días consecutivos. Dado que todos los monos tienen posiciones iniciales distintas y cada mono se mueve una posición a la derecha cada día cuando se lanza el hechizo, ningún par de monos estará en la misma posición en ningún día. Por lo tanto, ningún par de monos puede volverse amigo.
Entrada 3
6 7 1 1 8 16 18 22 RRLRLL
Salida 3
3
Entrada 4
10 30 9 46 27 8 12 100 56 96 6 7 LRLRRLRRLR
Salida 4
5
Entrada 5
4 2 3 4 4 6 LLRL
Salida 5
2
Nota
Hay $n = 4$ monos y Pan lanza el hechizo por $k = 2$ días consecutivos. Cada figura a continuación representa Monkeyland como una recta numérica que muestra posiciones del 1 al 6 solamente. La flecha sobre cada mono indica la dirección en la que se moverá después de lanzar el hechizo.
En el día 0, las posiciones iniciales de todos los monos se muestran en la figura a continuación. Los monos 2 y 3, que ya están en la posición 4, se vuelven amigos.
Después de que el hechizo ha sido lanzado en el día 1, las posiciones de todos los monos se muestran en la figura a continuación. Los monos 3 y 4 se encuentran en la posición 5 y se vuelven amigos.
Después de que el hechizo ha sido lanzado en el día 2, las posiciones de todos los monos se muestran en la figura a continuación. Ningún par de monos se encuentra en este día.
Por lo tanto, hay un total de 2 pares de monos que son amigos: los monos 2 y 3, así como los monos 3 y 4.