Monkeyland est une droite numérique infinie avec $n$ singes, numérotés de $1$ à $n$. Le $i$-ième singe est initialement à la position $p[i]$ sur la droite numérique. Il est possible que plusieurs singes partagent la même position initiale.
Pan peut faire bouger chaque singe avec son sortilège enchanteur ! La façon dont chaque singe se déplace est déterminée par une chaîne $d$ de longueur $n$ où chaque caractère est soit L, soit R. Soit $d[i]$ le $i$-ième caractère de $d$.
Une fois le sortilège lancé, le $i$-ième singe se déplace comme suit :
- Si $d[i] = \text{L}$, il se déplace vers la gauche d'une position.
- Si $d[i] = \text{R}$, il se déplace vers la droite d'une position.
Chaque jour, Pan lance son sortilège exactement une fois. Si deux singes se trouvent à la même position un jour donné (même initialement), ils deviennent amis. Si Pan devait lancer son sortilège pendant $k$ jours, déterminez le nombre de paires de singes qui deviendront amis.
Entrée
Votre programme doit lire depuis l'entrée standard.
La première ligne de l'entrée contient deux entiers séparés par un espace $n$ et $k$.
La deuxième ligne de l'entrée contient $n$ entiers séparés par un espace $p[1], p[2], \dots, p[n]$.
La troisième ligne de l'entrée contient une chaîne $d$ de $n$ caractères $d[1], d[2], \dots, d[n]$.
Sortie
Votre programme doit imprimer sur la sortie standard.
Affichez un seul entier, le nombre de paires de singes qui deviendront amis.
La sortie ne doit contenir qu'un seul entier. N'imprimez aucun texte supplémentaire tel que Enter a number ou The answer is.
Contraintes
Pour tous les cas de test, l'entrée satisfera les bornes suivantes :
- $1 \le n \le 200\,000$
- $1 \le k \le 10^9$
- $1 \le p[i] \le 10^9$ pour tout $1 \le i \le n$
- $d[i]$ est soit L soit R pour tout $1 \le i \le n$
Votre programme sera testé sur des instances d'entrée qui satisfont les restrictions suivantes :
| Sous-tâche | Score | Contraintes supplémentaires |
|---|---|---|
| 0 | 0 | Exemples de test |
| 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 | Aucune contrainte supplémentaire |
Exemples
Sample Test Case 1
Ce cas de test est valide pour les sous-tâches 1, 3, 4, 5 et 6.
Entrée 1
2 1 1 3 RL
Sortie 1
1
Remarque
Il y a $n = 2$ singes et Pan lance le sortilège pour $k = 1$ jour seulement. Le premier jour, le singe 1 se déplace vers la droite de la position 1 à la position 2 tandis que le singe 2 se déplace vers la gauche de la position 3 à la position 2. Comme ils finissent à la même position le premier jour, ils deviennent amis. Par conséquent, il y a exactement 1 paire de singes qui deviennent amis.
Sample Test Case 2
Ce cas de test est valide pour les sous-tâches 2, 3, 4, 5 et 6.
Entrée 2
5 67 1 2 3 4 5 RRRRR
Sortie 2
0
Remarque
Il y a $n = 5$ singes et Pan lance le sortilège pour $k = 67$ jours consécutifs. Comme tous les singes ont des positions initiales distinctes et que chaque singe se déplace d'une position vers la droite chaque jour lorsqu'un sortilège est lancé, aucun singe ne sera à la même position un jour donné. Par conséquent, aucune paire de singes ne peut devenir amie.
Sample Test Case 3
Ce cas de test est valide pour les sous-tâches 3, 4, 5 et 6.
Entrée 3
6 7 1 1 8 16 18 22 RRLRLL
Sortie 3
3
Sample Test Case 4
Ce cas de test est valide pour les sous-tâches 3, 4, 5 et 6.
Entrée 4
10 30 9 46 27 8 12 100 56 96 6 7 LRLRRLRRLR
Sortie 4
5
Sample Test Case 5
Ce cas de test est valide pour les sous-tâches 3, 4, 5 et 6.
Entrée 5
4 2 3 4 4 6 LLRL
Sortie 5
2
Remarque
Il y a $n = 4$ singes et Pan lance le sortilège pour $k = 2$ jours consécutifs. Chaque figure ci-dessous représente Monkeyland comme une droite numérique montrant les positions de 1 à 6 uniquement. La flèche au-dessus de chaque singe indique la direction dans laquelle il se déplacera après le lancement d'un sortilège.
Au 0-ième jour, les positions initiales de tous les singes sont indiquées dans la figure ci-dessous. Les singes 2 et 3 qui sont déjà à la position 4 deviennent amis.
Après que le sortilège a été lancé le 1-er jour, les positions de tous les singes sont indiquées dans la figure ci-dessous. Les singes 3 et 4 se rencontrent à la position 5 et deviennent amis.
Après que le sortilège a été lancé le 2-nd jour, les positions de tous les singes sont indiquées dans la figure ci-dessous. Aucun singe ne se rencontre ce jour-là.
Par conséquent, il y a un total de 2 paires de singes qui sont amis : les singes 2 et 3, ainsi que les singes 3 et 4.