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 = 2e5;
const int S = 450;
const uint8_t M = 101;
int n, m, l, r;
uint8_t a[N], x, y;
int st[S], en[S], bk[N];
list<int> b[S][M];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%hhu", a + i);
  int i = 0, j = 0, k = 0;
  while (i < n) {
    st[k] = i;
    while (j < n and j < i + S) {
      bk[j] = k;
      b[k][a[j]].push_back(j);
      ++j;
    }
    en[k] = j - 1;
    ++k;
    i = j;
  }
  scanf("%d", &m);
  while (m--) {
    scanf("%d %d %hhu %hhu", &l, &r, &x, &y);
    if (x == y) continue;
    --l;
    --r;
    for (int i = bk[l]; i <= bk[r]; ++i) {
      if (st[i] >= l and en[i] <= r) {
        b[i][y].splice(b[i][y].end(), b[i][x]);
      } else {
        auto it = b[i][x].begin();
        for (; it != b[i][x].end();) {
          auto jt = next(it);
          if (*it >= l and *it <= r) {
            b[i][y].splice(b[i][y].end(), b[i][x], it);
          }
          it = jt;
        }
      }
    }
  }
  for (int i = 1; i < M; ++i) {
    for (int j = 0; j < k; ++j) {
      for (int idx : b[j][i]) {
        a[idx] = i;
      }
    }
  }
  for (int i = 0; i < n; ++i) printf("%hhu ", a[i]);
  printf("\n");
  return 0;
}
