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>
#pragma comment(linker, "/STACK:66777216")
using namespace std;
const char SPACE = ' ', ENDL = '\n';
const int BASE = 1000 * 1000 * 1000 + 7;
const int MODULO = BASE;
template <class T>
T read() {
  T value;
  cin >> value;
  return value;
}
int read_int() { return read<int>(); }
size_t read_size() { return read<size_t>(); }
long long read_ll() { return read<long long>(); }
pair<int, int> read_ii() {
  int x = read_int();
  int y = read_int();
  return pair<int, int>(x, y);
}
string read_string() { return read<string>(); }
template <class T>
void read_vector(vector<T>& a, size_t size) {
  a.resize(size);
  for (T& value : a) cin >> value;
}
template <class T1, class T2>
void read_pairs(vector<pair<T1, T2>>& a, size_t size) {
  a.resize(size);
  for (auto& value : a) cin >> value.first >> value.second;
}
void read_graph(int n, int edges, vector<vector<int>>& graph,
                bool oriented = false) {
  graph.assign(n, vector<int>());
  for (int e = 0; e < edges; ++e) {
    int from = read_size() - 1;
    int to = read_size() - 1;
    graph[from].push_back(to);
    if (!oriented) graph[to].push_back(from);
  }
}
void read_tree(int n, vector<vector<int>>& graph) {
  read_graph(n, n - 1, graph);
}
void add_to_each(vector<int>& a, int delta) {
  for (int& value : a) value += delta;
}
void add_to_each(vector<pair<int, int>>& a, int delta) {
  for (pair<int, int>& value : a) {
    value.first += delta;
    value.second += delta;
  }
}
template <class T>
void print(T& a, char sep = ENDL) {
  cout << a << sep;
}
template <class T>
void print_vector(vector<T>& a, char sep = SPACE) {
  for (T& value : a) cout << value << sep;
  if (sep != ENDL) cout << ENDL;
}
template <class T>
void print_matrix(vector<vector<T>>& a, char sep = SPACE) {
  for (vector<T>& row : a) {
    print_vector(row, sep);
  }
}
void print_pairs(vector<pair<int, int>>& a, char sep = ENDL) {
  for (pair<int, int>& value : a)
    cout << value.first << " " << value.second << sep;
  if (sep != ENDL) cout << ENDL;
}
int get_bit(long long mask, int bit) { return (int)((mask >> bit) & 1); }
long long set_bit(long long mask, int bit) { return mask | (1LL << bit); }
long long clear_bit(long long mask, int bit) { return mask & (~(1LL << bit)); }
vector<int> reverse(vector<int>& a) {
  reverse(a.begin(), a.end());
  return a;
}
void update_max(long long& cur_value, long long new_value) {
  cur_value = max(cur_value, new_value);
}
void update_min(long long& cur_value, long long new_value) {
  cur_value = min(cur_value, new_value);
}
long long gcd(long long a, long long b) { return (a == 0 ? b : gcd(b % a, a)); }
long long lcm(long long a, long long b) {
  return (a * b == 0 ? 0 : a / gcd(a, b) * b);
}
bool check_index(int index, int size) { return 0 <= index && index < size; }
bool check_cell(int x, int xSize, int y, int ySize) {
  return check_index(x, xSize) && check_index(y, ySize);
}
void init() {}
int n;
vector<int> a;
int q;
vector<vector<int>> queries;
void read_input() {
  n = read_size();
  read_vector(a, n);
  add_to_each(a, -1);
  q = read_size();
  queries.assign(q, vector<int>());
  for (int i = 0; i < q; ++i) {
    read_vector(queries[i], 4);
    add_to_each(queries[i], -1);
  }
}
vector<int> get_answer() {
  int bs = 300;
  int bc = (n - 1) / bs + 1;
  const int maxC = 100;
  vector<vector<int>> heads(bc, vector<int>(maxC, -1));
  vector<vector<int>> lasts(bc, vector<int>(maxC, -1));
  vector<vector<int>> nexts(bc, vector<int>(maxC + maxC));
  auto icb = [&](int b) {
    for (int c = 0; c < maxC; ++c) {
      nexts[b][heads[b][c]] = c;
      nexts[b][c] = -1;
      lasts[b][c] = c;
    }
  };
  for (int b = 0; b < bc; ++b) {
    for (int c = 0; c < maxC; ++c) {
      heads[b][c] = c + maxC;
    }
    icb(b);
  }
  vector<int> b_st(bc + 1, 0);
  for (int b = 1; b <= bc; ++b) {
    b_st[b] = b_st[b - 1] + bs;
  }
  b_st[bc] = n;
  vector<int> tg(maxC, -1);
  auto pb = [&](int b) {
    for (int c = 0; c < maxC; ++c) {
      int h = heads[b][c];
      for (int v = nexts[b][h]; v != -1; v = nexts[b][v]) {
        tg[v] = c;
      }
    }
    for (int i = b_st[b]; i < b_st[b + 1]; ++i) {
      a[i] = tg[a[i]];
    }
    icb(b);
  };
  for (auto& query : queries) {
    const int left = query[0], right = query[1];
    const int fc = query[2], tc = query[3];
    if (fc == tc) continue;
    int lb = left / bs, rb = right / bs;
    if (lb == rb) {
      pb(lb);
      for (int i = left; i <= right; ++i) {
        if (fc == a[i]) a[i] = tc;
      }
    } else {
      pb(lb);
      for (int i = left; i < b_st[lb + 1]; ++i) {
        if (fc == a[i]) a[i] = tc;
      }
      pb(rb);
      for (int i = b_st[rb]; i <= right; ++i) {
        if (fc == a[i]) a[i] = tc;
      }
      for (int b = lb + 1; b < rb; ++b) {
        int fh = heads[b][fc];
        int ff = nexts[b][fh];
        if (-1 != ff) {
          int th = heads[b][tc];
          int tl = lasts[b][tc];
          nexts[b][tl] = ff;
          lasts[b][tc] = lasts[b][fc];
          nexts[b][fh] = -1;
          lasts[b][fc] = fh;
        }
      }
    }
  }
  for (int b = 0; b < bc; ++b) {
    pb(b);
  }
  return a;
}
void print_answer(vector<int> answer) {
  add_to_each(answer, 1);
  print_vector(answer);
}
void solve_test() {
  read_input();
  vector<int> answer = get_answer();
  print_answer(answer);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  init();
  int tests = 1;
  for (int test = 1; test <= tests; ++test) {
    solve_test();
  }
  return 0;
}
