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;
long long read() {
  long long a = 0, b = getchar(), c = 1;
  while (!isdigit(b)) c = b == '-' ? -1 : 1, b = getchar();
  while (isdigit(b)) a = a * 10 + b - '0', b = getchar();
  return a * c;
}
int n, q, ab, a[101], ans[200001], ls[8000001], rs[8000001], s[8000001];
void add(int& y, int l, int r, int x) {
  if (!y) y = ++ab;
  s[y]++;
  if (l == r) return;
  int mid = l + r >> 1;
  if (x <= mid)
    add(ls[y], l, mid, x);
  else
    add(rs[y], mid + 1, r, x);
}
void jj(int& y1, int& y2) {
  if (!y2) return;
  if (!y1) y1 = y2, y2 = 0;
  s[y1] += s[y2];
  jj(ls[y1], ls[y2]);
  jj(rs[y1], rs[y2]);
  y2 = 0;
}
void gg(int& y1, int& y2, int l, int r, int L, int R) {
  if (!y2) return;
  if (!y1) y1 = ++ab;
  if (L <= l and r <= R) {
    jj(y1, y2);
    return;
  }
  int mid = l + r >> 1;
  if (L <= mid) gg(ls[y1], ls[y2], l, mid, L, R);
  if (mid < R) gg(rs[y1], rs[y2], mid + 1, r, L, R);
  s[y1] = s[ls[y1]] + s[rs[y1]];
  s[y2] = s[ls[y2]] + s[rs[y2]];
}
void gao(int y, int l, int r, int va) {
  if (!s[y]) return;
  if (l == r) {
    ans[l] = va;
    return;
  }
  int mid = l + r >> 1;
  gao(ls[y], l, mid, va);
  gao(rs[y], mid + 1, r, va);
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) add(a[read()], 1, n, i);
  q = read();
  for (int i = 1; i <= q; i++) {
    int l = read(), r = read(), x = read(), y = read();
    if (x == y) continue;
    gg(a[y], a[x], 1, n, l, r);
  }
  for (int i = 1; i < 101; i++) gao(a[i], 1, n, i);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
