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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int block[200000 + 5], n, m, a[200000 + 5], t[100 + 5], p[(1 << 15) + 5];
struct Bitset {
  unsigned long long a[2];
  void Set(int x) { a[x >> 6] |= 1ULL << (x & 63); }
  void Clear() { a[0] = a[1] = 0; }
  void Change(int z) {
    int add = 64, y;
    unsigned long long x;
    for (x = a[1]; x;)
      if (x & 65535)
        y = x & 65535, y = y & (-y), t[p[y] + add] = z, x ^= y;
      else
        x >>= 16, add += 16;
    for (x = a[add = 0]; x;)
      if (x & 65535)
        y = x & 65535, y = y & (-y), t[p[y] + add] = z, x ^= y;
      else
        x >>= 16, add += 16;
  }
  void operator|=(const Bitset& y) {
    a[0] |= y.a[0];
    a[1] |= y.a[1];
  }
} s[450 + 5][100 + 5];
void Rebuild(int x) {
  int l = x * 450 - 450 + 1, r = min(n, x * 450);
  for (int i = 1; i <= 100; ++i)
    s[x][i].Change(i), s[x][i].Clear(), s[x][i].Set(i);
  for (int i = l; i <= r; ++i) a[i] = t[a[i]];
}
int main() {
  for (int i = 1, j = 0; j < 16; ++j, i <<= 1) p[i] = j;
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read(), block[i] = (i - 1) / 450 + 1;
  m = read();
  for (int i = 1; i <= block[n]; ++i)
    for (int j = 1; j <= 100; ++j) s[i][j].Set(j);
  for (int i = 1; i <= m; ++i) {
    int l = read(), r = read(), x = read(), y = read();
    if (x == y) continue;
    Rebuild(block[l]);
    for (int i = l; i <= r && block[i] == block[l]; ++i)
      if (a[i] == x) a[i] = y;
    if (block[l] != block[r]) {
      Rebuild(block[r]);
      for (int i = r; block[i] == block[r]; --i)
        if (a[i] == x) a[i] = y;
    }
    for (int i = block[l] + 1; i < block[r]; ++i)
      s[i][y] |= s[i][x], s[i][x].Clear();
  }
  for (int i = 1; i <= block[n]; ++i) Rebuild(i);
  for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
  return 0;
}
