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;
int n, q, x, y, l, r, a[200010], b[200010];
list<int> klist[500][110];
list<int>::iterator it, nit;
void build(int n) {
  for (int i = 1; i <= n; i++) {
    klist[i / 500][a[i]].emplace_back(i);
  }
}
void delblock(int l, int r, int b, int x, int y) {
  it = klist[b][x].begin();
  while (it != klist[b][x].end()) {
    nit = next(it);
    if (*it >= l && *it <= r) {
      klist[b][y].splice(klist[b][y].begin(), klist[b][x], it);
    }
    it = nit;
  }
}
void assign(int n) {
  int mb = n / 500;
  for (int i = 0; i <= mb; i++) {
    for (int j = 1; j < 110; j++) {
      for (int k : klist[i][j]) {
        b[k] = j;
      }
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  build(n);
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d%d%d", &l, &r, &x, &y);
    if (x == y) {
      continue;
    }
    int lb = l / 500, rb = r / 500;
    for (int i = lb + 1; i <= rb - 1; i++) {
      klist[i][y].splice(klist[i][y].begin(), move(klist[i][x]));
    }
    delblock(l, r, lb, x, y);
    if (lb != rb) {
      delblock(l, r, rb, x, y);
    }
  }
  assign(n);
  for (int i = 1; i <= n; i++) {
    printf("%d ", b[i]);
  }
  printf("\n");
  return 0;
}
