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
#include <bits/stdc++.h>
using namespace std;
int SET(int n, int pos) { return n = n | (1 << pos); }
int RESET(int n, int pos) { return n = n & ~(1 << pos); }
int CHECK(int n, int pos) { return (bool)(n & (1 << pos)); }
int bigMod(int n, int power, int MOD) {
  if (power == 0) return 1;
  if (power % 2 == 0) {
    int ret = bigMod(n, power / 2, MOD);
    return ((ret % MOD) * (ret % MOD)) % MOD;
  } else
    return ((n % MOD) * (bigMod(n, power - 1, MOD) % MOD)) % MOD;
}
int modInverse(int n, int MOD) { return bigMod(n, MOD - 2, MOD); }
int POW(int x, int y) {
  int res = 1;
  for (; y;) {
    if ((y & 1)) {
      res *= x;
    }
    x *= x;
    y >>= 1;
  }
  return res;
}
int inverse(int x) {
  double p = ((double)1.0) / x;
  return (p) + 1e-9;
}
int gcd(int a, int b) {
  while (b) b ^= a ^= b ^= a %= b;
  return a;
}
int nC2(int n) { return n * (n - 1) / 2; }
int MOD(int n, int mod) {
  if (n >= 0)
    return n % mod;
  else if (-n == mod)
    return 0;
  else
    return mod + (n % mod);
}
vector<int> vec[1000001], ans[1000001];
int vis[1000001];
int ara[1000001];
int ind[1000001];
int n, m;
bool ok = true;
void foo(int u, int num) {
  vis[u] = 1;
  for (int i = 0; i < vec[u].size(); i++) {
    int v = vec[u][i];
    if (!vis[v]) {
      ans[num].push_back(ara[v]);
      ind[v] = num;
      foo(v, num);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> ara[i];
  }
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  int level = 1;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      ans[level].push_back(ara[i]);
      ind[i] = level;
      foo(i, level);
      level++;
    }
  }
  for (int i = 1; i <= n; i++) {
    sort(ans[i].begin(), ans[i].end());
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[ind[i]].back() << " ";
    ans[ind[i]].pop_back();
  }
  return 0;
}
