Svetozar is the reigning world champion in the rock-paper-scissors game. Today the Candidates Tournament is taking place; its winner will challenge Svetozar for the next title.
Each match consists of a single round in which the players simultaneously choose one of the three options. As is well known, rock beats scissors, scissors beat paper, paper beats rock; if both players show the same action, the referee tosses a coin, and either player may become the winner with probability $$$\frac{1}{2}$$$.
The Candidates Tournament bracket is a binary tree of matches: the candidates stand at the leaves, and at each internal vertex the winners of its two subtrees play. Svetozar is not in the bracket, but his future match against the winner of the Candidates Tournament will follow the same rules.
For a fair and unbiased selection, the match tree is height-balanced, that is, for every vertex the heights of the subtrees differ by at most $$$1$$$.
Analysts from Svetozar's team have studied all games of the current season, and for each candidate the distribution with which he chooses rock, scissors, and paper is known. It may be assumed that a player follows his distribution in every match independently of who his opponent is.
Svetozar wants to know the probability that he wins if he now chooses rock, scissors, or paper as his action in the title match. Help him find these probabilities.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The first line of a test case contains an integer $$$n$$$ ($$$1 \leq n \lt 2 \cdot 10^5$$$): the number of vertices of the tree.
The next line contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters 'n' and 'p'. It describes the vertices of the tournament tree in the order of their first visit in a preorder traversal. The tree is built from this string as follows. Create a tree with a single root vertex and scan the characters of the string from left to right.
Then there is one line for each letter 'p' in $$$s$$$ (from left to right). Each such line contains integers $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ ($$$0 \leq a_i, b_i, c_i \leq 100$$$, $$$a_i + b_i + c_i = 100$$$): the probabilities that the corresponding candidate chooses rock, scissors, and paper, in percent.
It is guaranteed that in the string $$$s$$$ the number of letters 'p' equals the number of letters 'n' plus one.
It is guaranteed that the constructed tree is height-balanced, that is, for every vertex the heights of its left and right subtrees differ by at most $$$1$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print three integers: the probabilities that Svetozar can defeat the winner of the Candidates Tournament if he chooses rock, scissors, and paper against him, respectively, modulo $$$998\,244\,353$$$.
Formally, let $$$M = 998\,244\,353$$$. It can be shown that each value in the answer can be represented as an irreducible fraction $$$P / Q$$$, where $$$P$$$ and $$$Q$$$ are integers and $$$Q \not \equiv 0 \pmod{M}$$$. Instead of printing $$$f = P / Q$$$, print an integer $$$r$$$ such that $$$0 \leq r \lt M$$$ and $$$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
Note that the input lists probabilities in the order rock, scissors, and paper, which is not the same as in the name RPS (rock, paper, and scissors).
The answers for the test cases in decoded form: