Tree Coloring with Restrictions under Dynamic Queries

In the night sky, the fireworks bloom and connect into a tree of n nodes, with the earliest firework as the root (node 1). Each firework can be colored black or white. For convenience, the tree is re‐colored in black and white. Initially, there are p restrictions. Each restriction is given as a pair (x_i, y_i) meaning that in the subtree of node x_i, the number of black nodes must be exactly y_i.

A subtree is called uniformly good if all nodes with restrictions in that subtree satisfy their corresponding condition. Note that there may be multiple coloring methods available even if the restrictions are satisfied.

You are to answer the following two types of independent queries (each query does not affect the original tree):

• Z k c: For node k, a real number f is chosen uniformly at random from the set of integers in [0, c] (each integer with equal probability). Then, f new children (which are not subject to any restrictions) are added as direct children of node k (the other children remain unchanged). Compute the expected number of valid (uniformly good) colorings of the subtree rooted at k modulo 998244353 under this random addition.
• H k: Remove the restrictions from all direct children of node k (if any), and then compute the number of uniformly good colorings of the subtree rooted at k modulo 998244353.

Note: A valid coloring of a subtree means that for every node in that subtree which retains a restriction, the total number of black nodes in its own subtree is exactly equal to its prescribed value.

Since the number of possible fireworks (and hence the tree sizes) can be huge, you only need to compute the answer modulo the prime number 998244353.

inputFormat

The first line contains three integers n, p and q, where n is the number of nodes in the tree, p is the number of restrictions, and q is the number of queries.

If n > 1, the second line contains n-1 integers. The i-th integer (for i = 2,..., n) denotes the parent of node i.

The next p lines each contain two integers x and y, representing a restriction: in the subtree of node x, there must be exactly y black nodes.

The next q lines each describe a query in one of the following formats:

• H k
• Z k c

All queries are independent and do not modify the tree permanently.

outputFormat

For each query, output a single integer: the answer modulo 998244353.

sample

1 0 2

Z 1 0
H 1

2
2

</p>