Светозар — действующий чемпион мира по игре «камень, ножницы, бумага». Сегодня проходит турнир претендентов, по итогам которого определится победитель — именно он бросит Светозару вызов в борьбе за следующий титул.
Каждый матч в игре состоит из одного раунда, в котором игроки одновременно выбирают один из трёх вариантов. Как известно, камень побеждает ножницы, ножницы побеждают бумагу, бумага побеждает камень; если же оба игрока показали одно и то же действие, судья бросает монетку, и победителем может стать любой из игроков с вероятностью $$$\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'. Она описывает вершины дерева турнира при их первом посещении при прямом обходе. Дерево строится по этой строке следующим образом. Создадим дерево с единственной корневой вершиной и пробежимся по символам строки слева направо.
Далее следует по одной строке на каждую букву '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}$$$.
41p100 0 03npp100 0 00 100 03npp50 50 050 50 05npnpp67 13 2020 26 5410 11 79
499122177 0 1499122177 0 1249561089 748683265 499122177126346277 983129554 387890700
Ответы на тестовые случаи в декодированном виде: