You are given an array a consisting of n integers. You have to process q queries to this array; each query is given as four numbers l, r, x and y, denoting that for every i such that l ≤ i ≤ r and ai = x you have to set ai equal to y.

Print the array after all queries are processed.

Input

The first line contains one integer n (1 ≤ n ≤ 200000) — the size of array a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100) — the elements of array a.

The third line contains one integer q (1 ≤ q ≤ 200000) — the number of queries you have to process.

Then q lines follow. i-th line contains four integers l, r, x and y denoting i-th query (1 ≤ l ≤ r ≤ n, 1 ≤ x, y ≤ 100).

Output

Print n integers — elements of array a after all changes are made.

Example

Input

5
1 2 3 4 5
3
3 5 3 5
1 5 5 1
1 5 1 5


Output

5 2 5 4 5 
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int P = 455;
const int M = 105;
struct node {
  short x, y;
  node() {}
  node(int x, int y) : x(x), y(y) {}
};
int n, pc, T, l, r, x, y, m, mx = 100;
int bl[N], br[N], a[N], b[P][P], p[N], fa[M], len[P];
vector<node> c[P];
void init() {
  int i, j;
  for (i = 1; i <= n; i++) p[i] = (i - 1) / pc + 1;
  m = p[n];
  for (i = 1; i <= m; i++) bl[i] = (i - 1) * pc + 1;
  for (i = 1; i <= m; i++) br[i] = min(n, i * pc);
  for (i = 1; i <= m; i++) len[i] = br[i] - bl[i] + 1;
  for (i = 1; i <= m; i++)
    for (j = bl[i]; j <= br[i]; j++) b[i][j - bl[i] + 1] = a[j];
}
void update(int k) {
  int i;
  for (i = 1; i <= mx; i++) fa[i] = i;
  for (i = c[k].size() - 1; i >= 0; i--) fa[c[k][i].x] = fa[c[k][i].y];
  for (i = 1; i <= len[k]; i++) b[k][i] = fa[b[k][i]];
  c[k].clear();
}
int main() {
  int i, pl, pr, j;
  scanf("%d", &n);
  pc = sqrt(n);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  init();
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d%d", &l, &r, &x, &y);
    pl = p[l];
    pr = p[r];
    if (pl == pr) {
      update(pl);
      for (i = l; i <= r; i++)
        if (b[pl][i - bl[pl] + 1] == x) b[pl][i - bl[pl] + 1] = y;
      continue;
    }
    update(pl);
    for (i = l; i <= br[pl]; i++)
      if (b[pl][i - bl[pl] + 1] == x) b[pl][i - bl[pl] + 1] = y;
    update(pr);
    for (i = bl[pr]; i <= r; i++)
      if (b[pr][i - bl[pr] + 1] == x) b[pr][i - bl[pr] + 1] = y;
    for (i = pl + 1; i < pr; i++) c[i].push_back(node(x, y));
  }
  for (i = 1; i <= m; i++) {
    update(i);
    for (j = 1; j <= len[i]; j++) printf("%d ", b[i][j]);
  }
  return 0;
}
