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 q, n, A[200005];
struct no {
  int left, right, mid;
  short dis[101];
} node[200005 * 4];
void build(int left, int right, int x) {
  node[x].left = left, node[x].right = right;
  for (int i = 1; i <= 100; i++) node[x].dis[i] = i;
  if (left == right) return;
  int mid = (left + right) >> 1;
  node[x].mid = mid;
  build(left, mid, x << 1);
  build(mid + 1, right, x << 1 | 1);
}
void pushdown(int x) {
  for (int i = 1; i <= 100; i++) {
    node[x << 1].dis[i] = node[x].dis[node[x << 1].dis[i]];
    node[x << 1 | 1].dis[i] = node[x].dis[node[x << 1 | 1].dis[i]];
  }
  for (int i = 1; i <= 100; i++) node[x].dis[i] = i;
}
void work(int left, int right, int x, int fr, int to, int da) {
  if (node[x].left == left && node[x].right == right) {
    for (int i = 1; i <= 100; i++) {
      if (node[x].dis[i] == fr) {
        node[x].dis[i] = to;
      }
    }
    return;
  }
  pushdown(x);
  int mid = node[x].mid;
  if (left > mid)
    work(left, right, x << 1 | 1, fr, to, da);
  else if (right <= mid)
    work(left, right, x << 1, fr, to, da);
  else
    work(left, mid, x << 1, fr, to, da),
        work(mid + 1, right, x << 1 | 1, fr, to, da);
}
int get(int x, int to, int da) {
  if (node[x].left == node[x].right) {
    return node[x].dis[da];
  }
  pushdown(x);
  int mid = node[x].mid;
  if (to > mid)
    return get(x << 1 | 1, to, da);
  else
    return get(x << 1, to, da);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
  }
  scanf("%d", &q);
  build(1, n, 1);
  for (int i = 1; i <= q; i++) {
    int l, r, x, y;
    scanf("%d%d%d%d", &l, &r, &x, &y);
    work(l, r, 1, x, y, i);
  }
  for (int i = 1; i <= n; i++) {
    printf("%d ", get(1, i, A[i]));
  }
  return 0;
}
