L. Турнир претендентов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Светозар — действующий чемпион мира по игре «камень, ножницы, бумага». Сегодня проходит турнир претендентов, по итогам которого определится победитель — именно он бросит Светозару вызов в борьбе за следующий титул.

Каждый матч в игре состоит из одного раунда, в котором игроки одновременно выбирают один из трёх вариантов. Как известно, камень побеждает ножницы, ножницы побеждают бумагу, бумага побеждает камень; если же оба игрока показали одно и то же действие, судья бросает монетку, и победителем может стать любой из игроков с вероятностью $$$\frac{1}{2}$$$.

Сетка турнира претендентов — двоичное дерево матчей: претенденты стоят в листьях, а в каждой внутренней вершине играют победители двух её поддеревьев. Светозар в сетке отсутствует, но его будущий матч с победителем турнира претендентов будет проводиться по тем же правилам.

Для целей честного и непредвзятого отбора дерево матчей сбалансировано по высоте, то есть для каждой внутренней вершины высота поддеревьев отличается не больше чем на $$$1$$$.

Эксперты-аналитики из команды Светозара проанализировали все игры текущего сезона, и для каждого претендента известно распределение, с которым он выбирает камень, ножницы и бумагу. Можно считать, что игрок придерживается своего распределения в любом матче независимо от того, кто его соперник.

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

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.

Первая строка описания содержит целое число $$$n$$$ ($$$1 \leqslant n \lt 2 \cdot 10^5$$$) — количество вершин дерева.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$ из букв 'n' и 'p'. Она описывает вершины дерева турнира при их первом посещении при прямом обходе. Дерево строится по этой строке следующим образом. Создадим дерево с единственной корневой вершиной и пробежимся по символам строки слева направо.

  • Если очередной символ равен 'n', у текущей вершины появляются две дочерние вершины (левая и правая), и происходит переход в левую из них.
  • Если очередной символ равен 'p', текущая вершина — очередной претендент (лист дерева), и далее происходит переход к самой далёкой от корня (можно показать, что она определяется однозначно) ещё не рассмотренной вершине дерева среди оставшихся, если таковая имеется.

Далее следует по одной строке на каждую букву 'p' в $$$s$$$ (слева направо). Каждая такая строка содержит три целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$0 \leqslant a_i, b_i, c_i \leqslant 100$$$, $$$a_i + b_i + c_i = 100$$$) — вероятности выбора камня, ножниц и бумаги соответствующим претендентом в процентах.

Гарантируется, что в строке $$$s$$$ количество букв 'p' равно количеству букв 'n' плюс один.

Гарантируется, что построенное дерево является сбалансированным по высоте, то есть у каждой вершины высоты её левого и правого поддеревьев отличаются не больше чем на $$$1$$$.

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

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

Для каждого тестового случая выведите три целых числа — вероятности того, что Светозар сможет победить того, кто выиграет турнир претендентов, если выберет против него камень, ножницы и бумагу соответственно, по модулю $$$998\,244\,353$$$.

Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что каждое значение в ответе может быть представлено в виде несократимой дроби $$$P / Q$$$, где $$$P$$$ и $$$Q$$$ — целые числа и $$$Q \not \equiv 0 \pmod{M}$$$. Вместо значения $$$f = P / Q$$$ нужно вывести такое целое число $$$r$$$, что $$$0 \leqslant r \lt M$$$ и $$$r \cdot Q \equiv P \pmod{M}$$$.

Пример
Входные данные
4
1
p
100 0 0
3
npp
100 0 0
0 100 0
3
npp
50 50 0
50 50 0
5
npnpp
67 13 20
20 26 54
10 11 79
Выходные данные
499122177 0 1
499122177 0 1
249561089 748683265 499122177
126346277 983129554 387890700
Примечание

Ответы на тестовые случаи в декодированном виде:

  • на первый: $$$1/2$$$, $$$0$$$, $$$1$$$;
  • на второй: $$$1/2$$$, $$$0$$$, $$$1$$$;
  • на третий: $$$3/4$$$, $$$1/4$$$, $$$1/2$$$.