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>
int n, q, maxn;
int a[200005];
std::vector<int> v[1901][105];
inline void merge(std::vector<int> &v1, std::vector<int> &v2) {
  if (v1.size() < v2.size()) std::swap(v1, v2);
  v1.insert(v1.end(), v2.begin(), v2.end());
  v2.clear();
}
inline void assign(int i, int x, int y, int l, int r) {
  static int vis[105] = {};
  if ((i + 1) * maxn <= n) {
    for (int j = 1; j <= 100; j++) {
      for (int k : v[i][j]) vis[k] = j;
      v[i][j].clear();
      v[i][j].push_back(j);
    }
    for (int j = i * maxn; j < (i + 1) * maxn; j++) a[j] = vis[a[j]];
  }
  for (int j = l; j < r; j++)
    if (a[j] == x) a[j] = y;
}
int main() {
  scanf("%d", &n);
  maxn = sqrt(n * log2(n)) + 1;
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; (i + 1) * maxn <= n; i++)
    for (int j = 1; j <= 100; j++) v[i][j].push_back(j);
  for (scanf("%d", &q); q--;) {
    int l, r, x, y, L, R;
    scanf("%d%d%d%d", &l, &r, &x, &y);
    if (x != y) {
      l--;
      L = l / maxn, R = r / maxn;
      if (L != R) {
        assign(L, x, y, l, (L + 1) * maxn);
        for (int i = L + 1; i < R; i++) merge(v[i][y], v[i][x]);
        assign(R, x, y, R * maxn, r);
      } else
        assign(L, x, y, l, r);
    }
  }
  for (int i = 0; (i + 1) * maxn <= n; i++) assign(i, 0, 0, 0, 0);
  for (int i = 0; i < n; i++) printf("%d ", a[i]);
}
