No tag edit access

D. Swaps in Permutation

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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^{6}) — 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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2017 02:09:41 (p1).

Desktop version, switch to mobile version.

User lists

Name |
---|