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;
void read(bool out = 0) {}
class dsu {
 public:
  vector<int> par;
  vector<int> rank;
  vector<int> token;
  vector<int> color;
  bool changed;
  void init(int n) {
    par = vector<int>();
    token = vector<int>();
    color = vector<int>();
    for (int i = 0; i < n; i++)
      par.push_back(i), token.push_back(i), color.push_back(i);
    rank.assign(n, 0);
    changed = 0;
  }
  int find(int a) { return par[a] == a ? a : par[a] = find(par[a]); }
  bool isunion(int a, int b) { return find(a) == find(b); }
  void set_color(int x, int y) { color[find(x)] = y; }
  int get_color(int x) { return color[find(x)]; }
  void move_color(int x, int y) {
    if (x == y) return;
    changed = 1;
    if (token[x] == -1) {
      return;
    } else if (token[y] == -1) {
      set_color(token[x], y);
      token[y] = token[x];
      token[x] = -1;
      return;
    } else {
      union_sets(token[x], token[y]);
      set_color(token[y], y);
      token[x] = -1;
      return;
    }
  }
  void union_sets(int a, int b) {
    int n = find(a);
    int m = find(b);
    if (n != m) {
      if (rand() & 1)
        par[n] = m;
      else
        par[m] = n;
      if (rank[n] == rank[m]) rank[n]++;
    }
  }
};
vector<dsu> part;
int a[2 * 500009];
int T;
void push(int ind) {
  if (!part[ind].changed) return;
  for (int i = 0; i < T; i++) {
    a[T * ind + i] = part[ind].get_color(a[T * ind + i]);
  }
  part[ind].init(101);
}
void update(int l, int r, int x, int y) {
  int first_part = l / T;
  int second_part = r / T;
  if (first_part == second_part) {
    push(first_part);
    for (int i = l; i <= r; i++) {
      if (a[i] == x) a[i] = y;
    }
  } else {
    push(first_part);
    push(second_part);
    for (int i = l; i < T * (first_part + 1); i++) {
      if (a[i] == x) a[i] = y;
    }
    for (int i = T * second_part; i <= r; i++) {
      if (a[i] == x) a[i] = y;
    }
    for (int i = first_part + 1; i < second_part; i++) {
      part[i].move_color(x, y);
    }
  }
}
int main() {
  read(1);
  int n;
  scanf("%d", &n);
  T = sqrt(n);
  part = vector<dsu>(T + 3);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  for (int i = 0; i < T + 3; i++) part[i].init(101);
  int m;
  scanf("%d", &m);
  while (m--) {
    int l, r, x, y;
    scanf("%d %d %d %d", &l, &r, &x, &y);
    l--, r--;
    update(l, r, x, y);
  }
  for (int i = 0; i < T + 3; i++) {
    push(i);
  }
  for (int i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
}
