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 block_size = 512, no_of_blocks = 450, n, q;
vector<vector<list<int> > > block(no_of_blocks, vector<list<int> >(101));
vector<int> arr(2e5 + 5, 0);
void pre() {
  for (int i = 1; i <= n; i++) {
    block[(i - 1) >> 9][arr[i]].push_back(i);
  }
}
void fin() {
  for (int i = 0; i < no_of_blocks; i++) {
    for (int j = 1; j <= 100; j++) {
      for (auto& x : block[i][j]) arr[x] = j;
    }
  }
}
void update(int l, int r, int x, int y) {
  if (x == y) return;
  int idx = (l - 1) >> 9;
  list<int>::iterator prev, curr;
  list<int> temp;
  for (curr = block[idx][x].begin(); curr != block[idx][x].end();) {
    if (*curr < l)
      curr++;
    else if (*curr >= l && *curr <= r) {
      prev = curr;
      curr++;
      temp.splice(temp.begin(), block[idx][x], prev, curr);
    } else
      curr++;
  }
  block[idx][y].splice(block[idx][y].begin(), temp);
  int idx2 = (r - 1) / block_size;
  for (idx++; idx < idx2; idx++) {
    block[idx][y].splice(block[idx][y].begin(), block[idx][x]);
  }
  for (curr = block[idx][x].begin(); curr != block[idx][x].end();) {
    if (*curr < l)
      curr++;
    else if (*curr >= l && *curr <= r) {
      prev = curr;
      curr++;
      temp.splice(temp.begin(), block[idx][x], prev, curr);
    } else
      curr++;
  }
  block[idx][y].splice(block[idx][y].begin(), temp);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> arr[i];
  pre();
  cin >> q;
  while (q--) {
    int l, r, x, y;
    cin >> l >> r >> x >> y;
    update(l, r, x, y);
  }
  fin();
  for (int i = 1; i <= n; i++) cout << arr[i] << " ";
  return 0;
}
