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 a[1000005];
list<int> sq[505][101];
void apply(int bl, int id, int flag, int x, int y, int id2 = 0) {
  for (auto it = sq[bl][x].begin(); it != sq[bl][x].end();) {
    if ((flag == 1 && *it >= id) || (flag == 0 && *it <= id) ||
        (flag == 2 && *it >= id && *it <= id2)) {
      auto it2 = ++it;
      --it;
      sq[bl][y].splice(sq[bl][y].begin(), sq[bl][x], it);
      it = it2;
    } else {
      it++;
    }
  }
}
int main() {
  int i, j, k, l, m, n, t, r, cnt;
  int flag = 0;
  long long ans = 0, an = 0;
  t = 1;
  while (t--) {
    scanf("%d", &n);
    int fa = 401;
    for (i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      sq[i / fa][a[i]].push_back(i);
    }
    int q, x, y;
    scanf("%d", &q);
    while (q--) {
      scanf("%d", &l);
      scanf("%d", &r);
      scanf("%d", &x);
      scanf("%d", &y);
      if (x == y) continue;
      if (l / fa == r / fa) {
        apply(l / fa, l, 2, x, y, r);
      } else {
        apply(l / fa, l, 1, x, y);
        apply(r / fa, r, 0, x, y);
        for (i = l / fa + 1; i < r / fa; i++) {
          sq[i][y].splice(sq[i][y].begin(), sq[i][x]);
        }
      }
    }
    for (i = 0; i < 505; i++) {
      for (j = 0; j < 101; j++) {
        for (int it : sq[i][j]) {
          a[it] = j;
        }
      }
    }
    for (i = 1; i <= n; i++) {
      printf("%d ", a[i]);
    }
    printf("\n");
  }
}
