691_D. Swaps in Permutation
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.

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.

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
```python
# by the authority of GOD     author: manhar singh sachdev #
 
import os,sys
from io import BytesIO, IOBase
 
def solve(n,p,path):
    se, x, fin = [1] * (n + 1), 1, [0] * n
    while x != len(se):
        se[x], jj, curr, inde, vals = 0, 0, [x], [x - 1], [p[x - 1]]
        while jj != len(curr):
            zz = curr[jj]
            for y in path[zz]:
                if se[y]:
                    curr.append(y)
                    inde.append(y-1)
                    vals.append(p[y-1])
                    se[y] = 0
            jj += 1
        inde.sort()
        vals.sort()
        for ind, i in enumerate(inde):
            fin[i] = vals[-ind - 1]
        while x != n + 1 and not se[x]:
            x += 1
    for i in fin:
        print(i, end=' ')
 
def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    path = [[] for _ in range(n + 1)]
    for _ in range(m):
        u1, v1 = map(int, input().split())
        path[u1].append(v1)
        path[v1].append(u1)
    solve(n,p,path)
 
#Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
if __name__ == '__main__':
    main()
```