Swaps in Permutation - Problem

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

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 p_k=q_k for 1≤k<i and p_i<q_i.

Input

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

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

Each of the last m lines contains two integers (a_j,b_j) (1≤a_j,b_j≤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.

Example

Input

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

Output

7 8 9 4 5 6 1 2 3

2091: Swaps in Permutation

Description

Source/Category