Monkeyland — это бесконечная числовая прямая, на которой находятся $n$ обезьян, пронумерованных от 1 до $n$. $i$-я обезьяна изначально находится в позиции $p[i]$ на числовой прямой. Несколько обезьян могут находиться в одной и той же начальной позиции.
Пэн может заставить каждую обезьяну двигаться с помощью своего волшебного заклинания! То, как движется каждая обезьяна, определяется строкой $d$ длины $n$, где каждый символ — это либо L, либо R. Пусть $i$-й символ строки $d$ равен $d[i]$.
После произнесения заклинания $i$-я обезьяна движется следующим образом: Если $d[i] = \text{L}$, она перемещается влево на одну позицию. Если $d[i] = \text{R}$, она перемещается вправо на одну позицию.
Каждый день Пэн произносит свое заклинание ровно один раз. Если две обезьяны оказываются в одной и той же позиции в любой день (даже изначально), они становятся друзьями. Если Пэн будет произносить свое заклинание в течение $k$ дней, определите количество пар обезьян, которые станут друзьями.
Входные данные
Ваша программа должна считывать данные из стандартного потока ввода. Первая строка входных данных содержит два целых числа $n$ и $k$, разделенных пробелом. Вторая строка содержит $n$ целых чисел $p[1], p[2], \dots, p[n]$, разделенных пробелами. Третья строка содержит строку $d$ из $n$ символов $d[1], d[2], \dots, d[n]$.
Выходные данные
Ваша программа должна выводить данные в стандартный поток вывода. Выведите одно целое число — количество пар обезьян, которые станут друзьями. Вывод должен содержать только одно целое число. Не выводите никакого дополнительного текста, такого как "Enter a number" или "The answer is".
Ограничения
Для всех тестовых случаев входные данные удовлетворяют следующим ограничениям: $1 \le n \le 200\,000$ $1 \le k \le 10^9$ $1 \le p[i] \le 10^9$ для всех $1 \le i \le n$ $d[i]$ — это либо L, либо R для всех $1 \le i \le n$
Ваша программа будет протестирована на входных данных, удовлетворяющих следующим ограничениям:
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 0 | 0 | Примеры тестов |
| 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 | Нет дополнительных ограничений |
Примеры
Входные данные 1
2 1 1 3 RL
Выходные данные 1
1
Примечание
В данном случае $n = 2$ обезьяны, и Пэн произносит заклинание в течение $k = 1$ дня. В первый день обезьяна 1 перемещается вправо из позиции 1 в позицию 2, а обезьяна 2 перемещается влево из позиции 3 в позицию 2. Поскольку они оказываются в одной и той же позиции в первый день, они становятся друзьями. Таким образом, существует ровно 1 пара обезьян, которые становятся друзьями.
Входные данные 2
5 67 1 2 3 4 5 RRRRR
Выходные данные 2
0
Примечание
В данном случае $n = 5$ обезьян, и Пэн произносит заклинание в течение $k = 67$ дней подряд. Поскольку все обезьяны изначально находятся в разных позициях и каждая обезьяна перемещается на одну позицию вправо каждый день, когда произносится заклинание, ни одна пара обезьян не окажется в одной и той же позиции в любой из дней. Таким образом, ни одна пара обезьян не может стать друзьями.
Входные данные 3
6 7 1 1 8 16 18 22 RRLRLL
Выходные данные 3
3
Входные данные 4
10 30 9 46 27 8 12 100 56 96 6 7 LRLRRLRRLR
Выходные данные 4
5
Входные данные 5
4 2 3 4 4 6 LLRL
Выходные данные 5
2
Примечание
В данном случае $n = 4$ обезьяны, и Пэн произносит заклинание в течение $k = 2$ дней подряд.
На 0-й день начальные позиции всех обезьян показаны на рисунке ниже. Обезьяны 2 и 3, которые уже находятся в позиции 4, становятся друзьями.
На 0-й день начальные позиции всех обезьян показаны на рисунке ниже. Обезьяны 2 и 3, которые уже находятся в позиции 4, становятся друзьями.
После того как заклинание было произнесено в 1-й день, позиции всех обезьян показаны на рисунке ниже. Обезьяны 3 и 4 встречаются в позиции 5 и становятся друзьями.
После того как заклинание было произнесено в 1-й день, позиции всех обезьян показаны на рисунке ниже. Обезьяны 3 и 4 встречаются в позиции 5 и становятся друзьями.
После того как заклинание было произнесено во 2-й день, позиции всех обезьян показаны на рисунке ниже. Никакие две обезьяны не встречаются в этот день.
После того как заклинание было произнесено во 2-й день, позиции всех обезьян показаны на рисунке ниже. Никакие две обезьяны не встречаются в этот день.
Таким образом, всего существует 2 пары обезьян, которые являются друзьями: обезьяны 2 и 3, а также обезьяны 3 и 4.