Energy Flow on Directed Graph

You are given a directed graph with n nodes and m edges. Each node i has an initial energy a_i. The graph may contain multiple edges and self‐loops. In addition, every node is considered to have an extra self‐loop. That is, for each node i, if its out‐degree (i.e. the number of edges going out from it, d_i) is computed from the given edges, then at every second the energy at node i is divided equally into d_i+1 parts. One part flows to each of the nodes that are adjacent via an outgoing edge (each edge contributes separately) and one extra part flows back to i itself.

This distribution process occurs simultaneously for all nodes at every second. You are then given q queries. Each query contains a time t (in seconds) and your task is to compute the energy of each node after exactly t seconds. All calculations are performed modulo 998244353.

Formally, for each node i, let the number of edges from i to j be c_ij (if any self‐loop appears in the input, it is included in c_ii). Then the transition matrix A where

\( A_{ij} = \frac{c_{ij} + \delta(i=j)}{d_i+1} \)

with \(\delta(i=j)=1\) and 0 otherwise. The energy vector evolves as \( v_{t} = A^t \times v_0 \), where \( v_0 \) is the initial energy vector. Output the resulting energy for each node modulo 998244353.

inputFormat

The input begins with two integers n and m (1 ≤ n ≤ 100, 0 ≤ m), representing the number of nodes and edges respectively.

The next line contains n integers: a1 a2 ... an, where ai is the initial energy of node i.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n), representing a directed edge from node u to node v. Note that there may be multiple edges and self‐loops.

The next line contains an integer q (1 ≤ q), the number of queries. Then q lines follow, each containing a single integer t (t ≥ 0) representing the number of seconds.

outputFormat

For each query, output a single line containing n space‐separated integers, where the i^th integer is the energy at node i after exactly t seconds, computed modulo 998244353.

sample

3 3
1 2 3
1 2
2 3
3 1
2
1
2

2 499122178 499122179
2 748683267 249561090