Description

The cave Norton is in can be viewed as a tree formed by $n$ chambers and $n-1$ passages. Norton is in chamber $s$, and the treasure is in chamber $t$. In the treasure chamber there is a special magnet with a powerful magnetic field, and Norton also carries a small magnet made of the same material. The magnet in the treasure chamber has only one pole (N or S), and its pole never changes. Norton’s magnet also has only one pole (N or S), but at the start of each moment it switches poles with probability $p$ (N becomes S, S becomes N).

At each moment, Norton’s movement is determined by the pole of the treasure-chamber magnet and the pole of Norton’s magnet:

1. The two magnets have different poles. In this case, the magnets trigger an “attraction” effect. Norton will move, due to the attractive force, to the chamber adjacent to $s$ whose distance to $t$ is $-1$ (that is, the parent of $s$ when rooting the tree at $t$).

2. The two magnets have the same pole. In this case, the magnets trigger a “bounce” effect. Norton will, due to the repulsive force, move uniformly at random to one of the chambers adjacent to $s$ whose distance to $t$ is $+1$ (that is, any child of $s$ when rooting the tree at $t$). If there is no such chamber, a “stun” effect is triggered: in the next moment, Norton will not make any move, and will not perform any pole switching either.

After some investigation, Norton already knows the entire cave structure and the pole-switching probability $p$. To search for the treasure more effectively, each time he asks you a query: you need to answer, if initially Norton is in chamber $x$ with his magnet pole being $c_1$, and the treasure is in chamber $y$ with the chamber magnet pole being $c_2$, what is the expected number of moments until Norton can find the treasure.

Input Format

The first line contains three integers $n,q,p$, representing the number of chambers, the number of queries, and the pole-switching probability. The pole-switching probability is given as a probability modulo $998244353$.

The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is a passage between chambers $u$ and $v$. It is guaranteed that the final structure is a tree.

The next $q$ lines each contain, in order, a positive integer $x$, a character $c_1$, a positive integer $y$, and a character $c_2$, indicating one query, with meanings as above. It is guaranteed that $c_1,c_2$ are N or S.

Output Format

Output $q$ lines. Each line contains one non-negative integer, representing the query answer modulo $998244353$.

6 4 499122177
1 2
1 3
5 3
4 6
4 3
2 N 1 S
3 S 1 S
5 N 6 N
1 S 4 N

3
6
17
11

10 6 199648871
3 7
4 9
2 3
5 6
7 10
5 7
5 9
8 2
1 3
10 S 5 S
1 N 7 S
1 N 4 N
1 S 4 N
4 N 3 S
7 N 4 N

332748127
8
665496262
665496261
665496253
831870314

Hint

Explanation of Sample 1

The pole-switching probability at each moment is $\dfrac{1}{2}$.

The cave structure is as follows:

For query 1, at moment $1$ Norton has probability $\dfrac{1}{2}$ to move to $1$, and probability $\dfrac{1}{2}$ to trigger “stun” and enter moment $3$. At moment $3$, similarly, he has probability $\dfrac{1}{2}$ to move to $1$, and probability $\dfrac{1}{2}$ to trigger “stun” and enter moment $5$... The expected value is $1\times\dfrac{1}{2}+3\times\left(\dfrac{1}{2}\right)^2+5\times\left(\dfrac{1}{2}\right)^3+\ldots=3$.

Constraints

This problem uses bundled testdata.

• Subtask 1 ( $10\%$ ): $n,q\leq15$.
• Subtask 2 ( $20\%$ ): $n\leq10^3$.
• Subtask 3 ( $25\%$ ): For all queries, it is guaranteed that $y=1$.
• Subtask 4 ( $45\%$ ): No special restrictions.

For all testdata, $2\leq n\leq5\times 10^5,1\leq q\leq5\times10^5,1\leq u,v,x,y\leq n,x\neq y,2\leq p\leq998244352$.

The input size of this problem is large. Please use a fast input method.

Translated by ChatGPT 5