L. Candidates Tournament
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

Input

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.

  • If the next character is 'n', the current vertex gets two children (left and right), and we move to the left one.
  • If the next character is 'p', the current vertex is the next candidate (a leaf of the tree), and then we move to the vertex farthest from the root among the remaining vertices that have not yet been considered (it can be shown that this vertex is uniquely determined), if such a vertex exists.

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$$$.

Output

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}$$$.

Example
Input
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
Output
499122177 0 1
499122177 0 1
249561089 748683265 499122177
126346277 983129554 387890700
Note

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:

  • for the first: $$$1/2$$$, $$$0$$$, $$$1$$$;
  • for the second: $$$1/2$$$, $$$0$$$, $$$1$$$;
  • for the third: $$$3/4$$$, $$$1/4$$$, $$$1/2$$$.