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 root[500005 * 10];
int l[500000 * 10];
int r[500000 * 10];
int ans[500005];
int cnt = 0;
void update(int &rt, int L, int R, int val) {
  if (rt == -1) rt = ++cnt;
  if (L == R) {
    return;
  }
  int mid = (L + R) >> 1;
  if (mid >= val)
    update(l[rt], L, mid, val);
  else
    update(r[rt], mid + 1, R, val);
}
int Merge(int x, int y) {
  if (x == -1) return y;
  if (y == -1) return x;
  l[x] = Merge(l[x], l[y]);
  r[x] = Merge(r[x], r[y]);
  return x;
}
void change(int &rt, int &RT, int L, int R, int LL, int RR) {
  if (rt == -1) return;
  if (LL <= L && RR >= R) {
    RT = Merge(RT, rt);
    rt = -1;
    return;
  }
  if (RT == -1) RT = ++cnt;
  int mid = (L + R) >> 1;
  if (mid >= LL) change(l[rt], l[RT], L, mid, LL, RR);
  if (mid < RR) change(r[rt], r[RT], mid + 1, R, LL, RR);
}
void dfs(int rt, int L, int R, int val) {
  if (L == R) {
    ans[L] = val;
    return;
  }
  int mid = (L + R) >> 1;
  if (l[rt] != -1) dfs(l[rt], L, mid, val);
  if (r[rt] != -1) dfs(r[rt], mid + 1, R, val);
}
int n;
void PP() {
  for (int i = 1; i <= 100; i++) {
    if (root[i] != -1) {
      dfs(root[i], 1, n, i);
    }
  }
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  printf("\n");
}
int main() {
  scanf("%d", &n);
  memset(root, -1, sizeof root);
  memset(l, -1, sizeof l);
  memset(r, -1, sizeof r);
  for (int i = 0, x; i < n; i++) {
    scanf("%d", &x);
    update(root[x], 1, n, i + 1);
  }
  int m;
  scanf("%d", &m);
  while (m--) {
    int L, R, x, y;
    scanf("%d%d%d%d", &L, &R, &x, &y);
    if (x == y) continue;
    change(root[x], root[y], 1, n, L, R);
  }
  PP();
  return 0;
}
