Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Испытание любви
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

ErnKor ради жюльена готов на всё, даже плыть через болота, кишащие крокодилами. Мы решили проверить эту любовь. ErnKor нужно будет проплыть речку шириной $$$1$$$ метр и длиной $$$n$$$ метров.

Река очень холодная. Поэтому, суммарно (то есть на протяжении всего заплыва от $$$0$$$ до $$$n+1$$$) ErnKor в воде может проплыть не более чем $$$k$$$ метров. В реку для гуманности мы добавили не только крокодилов, но и бревна, по которым он может прыгать. Наше испытание заключается в следующем:

Изначально ErnKor находится на левом берегу, а попасть ему надо на правый. Они находятся на $$$0$$$ и на $$$n+1$$$-м метре соответственно. Реку можно представить как $$$n$$$ участков, каждый длиной в $$$1$$$ метр. В каждом участке есть или бревно 'L', или крокодил 'C', или просто вода 'W'. ErnKor может передвигаться следующим образом:

  • Если он на поверхности (то есть на берегу или на бревне), он может прыгнуть вперед не более чем на $$$m$$$ ($$$1 \le m \le 10$$$) метров (можно прыгать на берег, на бревно или в воду).
  • Если он в воде, он может только переплыть на следующий участок реки (или на берег, если он на $$$n$$$-м метре).
  • ErnKor нельзя попадать в участок с крокодилом каким-либо образом.

Определите, сможет ли ErnKor добраться до правого берега.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$)  — количество наборов входных данных.

В первой строке каждого набора вводится три числа $$$n, m, k$$$ ($$$0 \le k \le 2 \cdot 10^5$$$, $$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10$$$) — длина реки, дальность прыжка ErnKor и количество метров, которое может проплыть ErnKor не замерзнув.

Во второй строке каждого набора вводится одна строка $$$a$$$ длины $$$n$$$. $$$a_i$$$ обозначает объект, находящийся на $$$i$$$-м метре. ($$$a_i \in \{$$$'W','C','L'$$$\}$$$)

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если ErnKor сможет выполнить испытание, и выведите «NO» в обратном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
6
6 2 0
LWLLLW
6 1 1
LWLLLL
6 1 1
LWLLWL
6 2 15
LWLLCC
6 10 0
CCCCCC
6 6 1
WCCCCW
Выходные данные
YES
YES
NO
NO
YES
YES
Примечание

Рассмотрим примеры:

  • Первый пример: С берега прыгаем на первое бревно ($$$0 \rightarrow 1$$$), с первого бревна прыгаем на второе ($$$1 \rightarrow 3$$$), со второго прыгаем на четвертое ($$$3 \rightarrow 5$$$), с последнего бревна прыгаем на берег ($$$5 \rightarrow 7$$$). Итого, пусть есть, $$$0 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 7$$$. Так как мы не заплыли на крокодила и проплыли в воде не больше k метров, ответ «YES».
  • Второй пример: $$$0 \rightarrow 1$$$, с первого бревна прыгаем в воду ($$$1 \rightarrow 2$$$), плывем клетку до бревна ($$$2 \leadsto 3$$$), $$$3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7$$$. Так как мы не заплыли на крокодила и проплыли в воде не больше k метров, ответ «YES».
  • В третьем примере ErnKor необходимо проплыть две клетки 'W', а может проплыть только одну. Поэтому ответ «NO»
  • Шестой пример: прыгаем с берега в воду ($$$0 \rightarrow 6$$$) и проплываем одну клетку воды ($$$6 \leadsto 7$$$). Так как мы не заплыли на крокодила и проплыли в воде не больше k метров, ответ «YES».