Directed Graph Outgoing Edges Sorted by Destination Weights

You are given a directed graph \(G\) with \(n\) vertices and \(m\) edges. The vertices are numbered from \(1\) to \(n\), and each vertex \(i\) has an associated weight \(w_i\). You are also given \(m\) directed edges.

For each vertex \(u = 1, 2, \dots, n\), consider all outgoing edges from \(u\) (i.e. edges originating from \(u\)). For each vertex \(u\), output the destination vertex numbers of its outgoing edges, sorted in ascending order according to the destination's weight \(w\). If two destinations have the same weight, the vertex with the smaller number should come first.

The output should be produced in the order of vertices \(1, 2, \dots, n\) by concatenating the sorted lists for each vertex.

Input Format: The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers, where the \(i\)th integer is \(w_i\). Each of the next \(m\) lines contains two integers \(u\) and \(v\), representing a directed edge from \(u\) to \(v\>.

Output Format: Print the destination vertex numbers by processing vertices \(1\) to \(n\) in order. For each vertex, list the destination vertices of its outgoing edges sorted by their weights (and by vertex number if weights are equal). All the numbers should be printed on a single line separated by spaces.

inputFormat

The input consists of multiple lines:

• The first line contains two integers \(n\) and \(m\) (\(1 \leq n \leq 10^5\), \(0 \leq m \leq 10^5\)).
• The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) representing the weights of the vertices.
• Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating a directed edge from vertex \(u\) to vertex \(v\).

outputFormat

Output a single line containing the destination vertices for all outgoing edges of vertices \(1\) to \(n\) in order, sorted for each vertex as described. Separate numbers with a space. If a vertex has no outgoing edges, output nothing for that vertex.

sample

4 4
40 10 30 20
1 2
1 3
2 4
3 4

2 3 4 4