#P691D. Swaps in Permutation

    ID: 3591 Type: RemoteJudge 5000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>dfs and similardsumath*1700

Swaps in Permutation

No submission language available for this problem.

Description

You are given a permutation of the numbers 1, 2, ..., n and m pairs of positions (aj, bj).

At each step you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation one can get?

Let p and q be two permutations of the numbers 1, 2, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so pk = qk for 1 ≤ k < i and pi < qi.

The first line contains two integers n and m (1 ≤ n, m ≤ 106) — the length of the permutation p and the number of pairs of positions.

The second line contains n distinct integers pi (1 ≤ pi ≤ n) — the elements of the permutation p.

Each of the last m lines contains two integers (aj, bj) (1 ≤ aj, bj ≤ n) — the pairs of positions to swap. Note that you are given a positions, not the values to swap.

Print the only line with n distinct integers p'i (1 ≤ p'i ≤ n) — the lexicographically maximal permutation one can get.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 106) — the length of the permutation p and the number of pairs of positions.

The second line contains n distinct integers pi (1 ≤ pi ≤ n) — the elements of the permutation p.

Each of the last m lines contains two integers (aj, bj) (1 ≤ aj, bj ≤ n) — the pairs of positions to swap. Note that you are given a positions, not the values to swap.

Output

Print the only line with n distinct integers p'i (1 ≤ p'i ≤ n) — the lexicographically maximal permutation one can get.

Samples

9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9

7 8 9 4 5 6 1 2 3