Паулина приехала на конференцию по фрагментации файловых систем в университет Иннополис на автомобиле. Парковка университета представляет из себя полосу ширины $n$ метров, на которой параллельно друг другу стоят транспортные средства. На ней могут парковаться владельцы автомобилей и мотоциклов. Кроме того, вся парковка разделена на $n$ зон ширины 1 метр. Водители уважают друг друга и паркуются по разделителям: мотоцикл занимает одну зону ширины 1 метр, а автомобиль – две соседние зоны суммарной ширины 2 метра.

Паулина хочет въехать на парковку. В данный момент, некоторые зоны заняты транспортными средствами. Также, у парковки собралась очередь на въезд из $m$ транспортных средств, не считая автомобиля Паулины. Все транспортные средства по очереди будут въезжать на парковку, и занимать любое свободное место: одну зону, если это мотоцикл, и две соседние зоны, если это автомобиль. Если водитель не может найти ни одного свободного места для своего транспортного средства, то он покидает Иннополис, не занимая места на парковке.

Паулине скоро выступать на конференции, и так как в Иннополисе люди очень вежливые, все в очереди готовы пропустить Паулину на парковку перед собой, чтобы она успела на свой доклад. Паулина не хочет пользоваться своим положением, но опасается, что если мест на парковке не хватит, то на доклад она точно не попадет. Так как Паулина эксперт во фрагментации файловых систем, она понимает, что транспортные средства не всегда удачно занимают места на парковке, и ей может не остаться места. Она смогла быстро понять, заехав перед кем в очереди, она гарантирует своему автомобилю свободное место на парковке.

Вам задано, какие из $n$ зон на парковке заняты, а также очередь из $m$ мотоциклов и автомобилей, не считая автомобиля Паулины. Требуется понять для каждого $i$ от 0 до $m$, останется ли место для автомобиля Паулины, если она въедет на парковку после первых $i$ транспортных средств из очереди, вне зависимости от того, какие зоны они займут.

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

Вам нужно будет решить несколько тестов.

В первой строке задано целое число $t$ – число тестов во входных данных ($1 \le t \le 50\,000$).

Далее заданы $t$ тестов, каждый из которых состоит из двух строк.

В первой из этих строк записано $n$ символов . и X, $i$-й из которых описывает $i$-ю зону: . для свободной зоны и X – для занятой ($1 \le n \le 10^5$).

Во второй из этих строк записано $m$ заглавных букв английского алфавита C и M, описывающих очередь из автомобилей C и мотоциклов M ($1 \le m \le n$). Первая буква соответствует началу очереди, а последняя – концу.

Сумма $n$ по $t$ заданным тестам не превосходит $5 \cdot 10^5$.

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

Выведите $t$ строк: по одному для каждого теста.

Строка должна содержать $m + 1$ заглавных букв английского алфавита Y и N, для каждого $i$ от 0 до $m$ запишите Y, если Паулина найдет место для своего автомобиля, въехав на парковку после $i$ первых транспортных средств из очереди, вне зависимости от того, какие зоны они займут, и N в противном случае.

Подзадачи