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;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 1e9 + 7;
const long long maxn = 1e6 + 7;
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = 1ll * a * a % M)
    if (b & 1) ret = 1ll * ret * a % M;
  return ret;
}
int a[maxn];
const int SIZE = 450;
int block[maxn];
int n, k, i, q;
int L[507], R[507];
vector<pair<char, char> > g[maxn];
int f[107];
void change(int x) {
  int i;
  for (i = 1; i <= 100; i++) f[i] = i;
  for (i = g[x].size() - 1; i >= 0; i--) {
    auto now = g[x][i];
    f[now.first] = f[now.second];
  }
  for (i = L[x]; i <= R[x]; i++) a[i] = f[a[i]];
  g[x].clear();
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (i = 1; i <= n; i++) {
    block[i] = i / SIZE;
    if (!L[i / SIZE]) L[i / SIZE] = i;
    R[i / SIZE] = i;
  }
  scanf("%d", &q);
  while (q--) {
    int l, r, x, y;
    scanf("%d%d%d%d", &l, &r, &x, &y);
    change(block[l]);
    change(block[r]);
    for (; l <= r && l != L[block[l]]; l++)
      if (a[l] == x) a[l] = y;
    for (; l <= r && r != R[block[r]]; r--)
      if (a[r] == x) a[r] = y;
    if (l <= r) {
      l = block[l];
      r = block[r];
      for (i = l; i <= r; i++) g[i].push_back(make_pair(x, y));
    }
  }
  for (i = 0; i <= n / SIZE; i++) change(i);
  for (i = 1; i <= n; i++) printf("%d ", a[i]);
}
