Блэк & Уайт
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В новом регионе Сэм обнаружил $$$n + 1$$$ городов, соединенных двусторонними дорогами. Причем, $$$n$$$ из этих городов расположены на окружности, а один город является столицей и расположен в центре. Пронумеруем города на окружности от $$$1$$$ до $$$n$$$ в порядке обхода, и назначим столице номер $$$n + 1$$$. Каждая дорога либо соединяет столицу с городом на окружности, либо соединяет два соседних города на окружности. Иными словами, дорога соединяет города $$$(n + 1)$$$ и $$$v$$$ или города $$$v$$$ и $$$(v \bmod n + 1)$$$, где $$$v \in [1, n]$$$.

Каждая дорога контролируется одной из конкурирующих банд: либо бандой Уайта, либо бандой Блэка. Сэм хочет выбрать и обезопасить минимальное количество дорог, по которым можно было бы добраться от любого города до любого другого. Другими словами, Сэм хочет выбрать остовное дерево в графе городов. Можно доказать, что любое остовное дерево будет содержать ровно $$$n$$$ дорог.

Для того, чтобы обезопасить дорогу, нужно договориться с главарём банды, контролирующей эту дорогу. Сэм ещё не знает, кто из Уайта и Блэка окажется сговорчивее, поэтому попросил вас для каждого целого $$$k \in [0, n]$$$ посчитать количество способов выбрать остовное дерево, чтобы ровно $$$k$$$ из выбранных дорог контролировались бандой Уайта, а $$$n - k$$$ оставшихся дорог — бандой Блэка. Так как ответы могут быть большими, посчитайте их по модулю $$$998\,244\,353$$$.

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

В первой строке дано одно целое число $$$n$$$ ($$$3 \le n \le 50\,000$$$).

Во второй строке дана строка $$$s$$$, состоящая из $$$n$$$ символов, описывающая дороги между городами на окружности. Если $$$s_i$$$ равно «-», дорога между городами $$$i$$$ и $$$(i \bmod n + 1)$$$ отсутствует, если «W» — дорога контролируется бандой Уайта, и если «B» — бандой Блэка.

В третьей строке дана строка $$$t$$$, состоящая из $$$n$$$ символов, описывающая дороги между столицей и городами на окружности. Если $$$t_i$$$ равно «-», дорога между столицей и городом $$$i$$$ отсутствует, если «W» — дорога контролируется бандой Уайта, и если «B» — бандой Блэка.

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

Выведите $$$n + 1$$$ целое число $$$a_k$$$ — $$$k$$$-е из них должно равняться количеству остовных деревьев графа городов, в которых ровно $$$k$$$ дорог контролируются бандой Уайта.

Примеры

Входные данные
3
---
WBW
Выходные данные
0 0 1 0 
Входные данные
3
WWW
BBB
Выходные данные
1 6 9 0 
Входные данные
5
BWB-B
WB-W-
Выходные данные
0 2 6 3 0 0 
Входные данные
4
----
----
Выходные данные
0 0 0 0 0