Evoking Memories

You are given n memories, each with an importance coefficient \(k_i\). There are m directed relationships among these memories. Each relationship \(u, v\) (with \(1 \le u,v \le n\)) indicates that the memory \(u\) happened immediately before the memory \(v\). Note that due to the passage of time, the timeline may have cycles.

Initially, every memory has a weight of \(0\). You will perform T operations. In the t-th operation, the updates happen in two phases:

1. Prior to the operation, for each memory \(x_i\) the current weight is stored as a backup. Then, every memory \(x_i\) has its weight multiplied by its coefficient \(k_i\); that is, the new weight becomes \(\text{weight}[i] \times k_i\).
2. During the operation, for each memory \(x_i\):
   • If exactly one memory \(y_i\) directly precedes \(x_i\) (i.e. there is exactly one incoming edge to \(x_i\)), then add the previous weight of \(y_i\) (before multiplication in this operation) to \(x_i\)'s weight.
   • If \(x_i\) has no incoming edge or has more than one incoming edge, then add the current operation index \(t\) to \(x_i\)'s weight.

As the weights may grow very large, output the final weight of every memory modulo \(998244353\) after performing all T operations.

inputFormat

The first line contains three integers \(n\), \(m\), and \(T\) separated by spaces.

The second line contains \(n\) integers: \(k_1, k_2, \dots, k_n\), where \(k_i\) is the importance coefficient for the \(i\)-th memory.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating that memory \(u\) happened immediately before memory \(v\). There are no multiple edges.

outputFormat

Output a single line containing \(n\) integers — the final weights of the memories in order from \(1\) to \(n\), each taken modulo \(998244353\).

sample

3 2 2
2 3 4
1 2
2 3

4 1 0