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;
int segtree[1 << 19][101];
inline void push(int i) {
  if (i >= 1 << 18) return;
  for (int j = 1; j <= 100; ++j) {
    segtree[2 * i][j] = segtree[i][segtree[2 * i][j]];
    segtree[2 * i + 1][j] = segtree[i][segtree[2 * i + 1][j]];
  }
  for (int j = 1; j <= 100; ++j) segtree[i][j] = j;
}
void upd(int i, int l1, int r1, int l2, int r2, int x, int y) {
  if (l2 <= l1 && r1 <= r2) {
    for (int j = 1; j <= 100; ++j)
      if (segtree[i][j] == x) segtree[i][j] = y;
    return;
  }
  push(i);
  int m = (l1 + r1) / 2;
  if (l2 <= m) upd(2 * i, l1, m, l2, r2, x, y);
  if (m < r2) upd(2 * i + 1, m + 1, r1, l2, r2, x, y);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i < 1 << 19; ++i)
    for (int j = 1; j <= 100; ++j) segtree[i][j] = j;
  int n, q;
  cin >> n;
  a = new int[n];
  for (int i = 0; i < n; ++i) cin >> a[i];
  cin >> q;
  while (q--) {
    int l, r, x, y;
    cin >> l >> r >> x >> y;
    upd(1, 0, (1 << 18) - 1, l - 1, r - 1, x, y);
  }
  for (int i = 1; i < 1 << 18; ++i) push(i);
  for (int i = 0; i < n; ++i) cout << segtree[(1 << 18) + i][a[i]] << " ";
}
