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 \le i \le n exists, so pk=qk for 1 \le k \lt i and pi \lt qi.

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

The second line contains n distinct integers pi (1 \le pi \le n) - the elements of the permutation p.

Each of the last m lines contains two integers (aj,bj) (1 \le aj,bj \le 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 \le p'i \le n) - the lexicographically maximal permutation one can get.