Monkeyland to nieskończona oś liczbowa, na której znajduje się $n$ małp, ponumerowanych od $1$ do $n$. $i$-ta małpa znajduje się początkowo w pozycji $p[i]$ na osi liczbowej. Możliwe jest, że wiele małp zajmuje tę samą pozycję początkową.
Pan może sprawić, że każda małpa wykona ruch za pomocą swojego czarującego zaklęcia! Sposób poruszania się każdej małpy jest określony przez ciąg $d$ o długości $n$, w którym każdy znak to albo L, albo R. Niech $d[i]$ oznacza $i$-ty znak ciągu $d$.
Po rzuceniu zaklęcia $i$-ta małpa porusza się w następujący sposób: Jeśli $d[i] = \text{L}$, przesuwa się w lewo o jedną pozycję. Jeśli $d[i] = \text{R}$, przesuwa się w prawo o jedną pozycję.
Każdego dnia Pan rzuca swoje zaklęcie dokładnie raz. Jeśli dwie małpy znajdują się w tej samej pozycji w dowolnym dniu (nawet początkowo), zostają przyjaciółmi. Jeśli Pan rzucałby swoje zaklęcie przez $k$ dni, określ liczbę par małp, które zostaną przyjaciółmi.
Wejście
Twój program musi czytać dane ze standardowego wejścia. Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ oraz $k$ oddzielone spacją. Druga linia wejścia zawiera $n$ liczb całkowitych $p[1], p[2], \dots, p[n]$ oddzielonych spacjami. Trzecia linia wejścia zawiera ciąg $d$ składający się z $n$ znaków $d[1], d[2], \dots, d[n]$.
Wyjście
Twój program musi wypisać wynik na standardowe wyjście. Wypisz jedną liczbę całkowitą, liczbę par małp, które zostaną przyjaciółmi. Wyjście powinno zawierać tylko jedną liczbę całkowitą. Nie wypisuj żadnego dodatkowego tekstu.
Podzadania
Dla wszystkich przypadków testowych dane wejściowe spełniają następujące ograniczenia: $1 \le n \le 200\,000$ $1 \le k \le 10^9$ $1 \le p[i] \le 10^9$ dla wszystkich $1 \le i \le n$ $d[i]$ jest równe L lub R dla wszystkich $1 \le i \le n$
Twój program będzie testowany na instancjach wejściowych spełniających następujące ograniczenia:
| Podzadanie | Wynik | Dodatkowe ograniczenia |
|---|---|---|
| 0 | 0 | Przykładowe przypadki testowe |
| 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 | Brak dodatkowych ograniczeń |
Przykład
Wejście 1
2 1 1 3 RL
Wyjście 1
1
Uwagi
Jest $n = 2$ małp, a Pan rzuca zaklęcie tylko na $k = 1$ dzień. Pierwszego dnia małpa 1 przesuwa się w prawo z pozycji 1 na pozycję 2, podczas gdy małpa 2 przesuwa się w lewo z pozycji 3 na pozycję 2. Ponieważ kończą na tej samej pozycji pierwszego dnia, zostają przyjaciółmi. Zatem istnieje dokładnie 1 para małp, które zostają przyjaciółmi.
Wejście 2
5 67 1 2 3 4 5 RRRRR
Wyjście 2
0
Uwagi
Jest $n = 5$ małp, a Pan rzuca zaklęcie przez $k = 67$ kolejnych dni. Ponieważ wszystkie małpy mają różne pozycje początkowe i każda małpa przesuwa się o jedną pozycję w prawo każdego dnia, gdy rzucane jest zaklęcie, żadne dwie małpy nie znajdą się w tej samej pozycji w żadnym dniu. Zatem żadne pary małp nie mogą zostać przyjaciółmi.
Wejście 3
6 7 1 1 8 16 18 22 RRLRLL
Wyjście 3
3
Wejście 4
10 30 9 46 27 8 12 100 56 96 6 7 LRLRRLRRLR
Wyjście 4
5
Wejście 5
4 2 3 4 4 6 LLRL
Wyjście 5
2
Uwagi
Jest $n = 4$ małp, a Pan rzuca zaklęcie przez $k = 2$ kolejne dni. Każdy rysunek poniżej przedstawia Monkeyland jako oś liczbową pokazującą pozycje tylko od 1 do 6. Strzałka nad każdą małpą wskazuje kierunek, w którym poruszy się ona po rzuceniu zaklęcia.
W dniu 0 początkowe pozycje wszystkich małp są pokazane na poniższym rysunku. Małpy 2 i 3, które już znajdują się na pozycji 4, zostają przyjaciółmi.
Po rzuceniu zaklęcia w dniu 1, pozycje wszystkich małp są pokazane na poniższym rysunku. Małpy 3 i 4 spotykają się na pozycji 5 i zostają przyjaciółmi.
Po rzuceniu zaklęcia w dniu 2, pozycje wszystkich małp są pokazane na poniższym rysunku. Żadne dwie małpy nie spotykają się tego dnia.
Dlatego istnieje łącznie 2 pary małp, które są przyjaciółmi: małpy 2 i 3 oraz małpy 3 i 4.