G. Order Statistics on the Graph
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a directed graph with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Each vertex has at least one incoming edge. The graph may contain self-loops, but it has no multiple edges. For each vertex $$$v$$$, an integer $$$k_v$$$ is given, ranging from $$$1$$$ to the number of incoming edges of that vertex.

Each vertex has a number written on it. Every second, all the numbers are updated as follows. For a vertex $$$v$$$, take the numbers at the vertices $$$u$$$ for which there is an edge $$$u\to v$$$, sort them in non-decreasing order, and update vertex $$$v$$$ with the number at the position $$$k_v$$$. Positions in the sorted list are numbered starting from $$$1$$$. In other words, the new number at vertex $$$v$$$ is the $$$k_v$$$-th order statistic of the array consisting of the numbers at the vertices $$$u$$$ for which there is an edge $$$u \to v$$$.

All vertices are updated simultaneously: only the numbers from before the current update are used to compute the new numbers. If a vertex has a self-loop, its own number also affects the update.

You have to process $$$q$$$ queries of the following form:

  • $$$t$$$ $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$ — determine the numbers that will be written on the vertices of the graph after $$$t$$$ seconds if their initial numbers are $$$a_1, a_2, \dots, a_n$$$.
Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1\le n\le20$$$; $$$n\le m\le n^2$$$; $$$1\le q\le10^5$$$) — the number of vertices, edges, and queries, respectively.

The second line contains $$$n$$$ integers $$$k_1,k_2,\ldots,k_n$$$. For each vertex $$$v$$$, it holds that $$$1\le k_v\le d_v$$$, where $$$d_v$$$ is the number of incoming edges of that vertex.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$), denoting an edge from $$$u$$$ to $$$v$$$. All ordered pairs $$$(u,v)$$$ are distinct.

Each of the next $$$q$$$ lines contains $$$n+1$$$ integers $$$t,a_1,a_2,\ldots,a_n$$$ ($$$0\le t\le10^{18}$$$; $$$1\le a_i\le10^9$$$) — the parameters of a query.

Output

For each query, print $$$n$$$ integers — the values on vertices $$$1,2,\dots,n$$$ after $$$t$$$ seconds.

Examples
Input
3 3 4
1 1 1
1 2
2 3
3 1
0 4 8 15
1 4 8 15
2 4 8 15
1000000000000000000 1 2 3
Output
4 8 15
15 4 8
8 15 4
3 1 2
Input
2 4 3
1 2
1 1
1 2
2 1
2 2
1 10 1
1000000000000000000 7 7
0 1000000000 1
Output
1 10
7 7
1000000000 1
Input
4 8 4
1 2 2 1
1 1
2 1
1 2
2 2
3 2
2 3
4 3
3 4
1 8 3 5 1
2 8 3 5 1
3 8 3 5 1
1000000000000000000 8 3 5 1
Output
3 5 3 5
3 3 5 3
3 3 3 5
3 3 5 3
Note

In the first example, each number moves to the next vertex of the cycle. After three seconds, all numbers return to their original positions.

In the second example, the first vertex takes the minimum of the two numbers, while the second takes the maximum.

In the third example, the array $$$[8,3,5,1]$$$ becomes $$$[3,5,3,5]$$$ after the first update and $$$[3,3,5,3]$$$ after the second update.