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 GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
int read_int() {
  bool minus = false;
  int result = 0;
  char ch;
  ch = getchar();
  while (1) {
    if (ch == '-') break;
    if (ch >= '0' && ch <= '9') break;
    ch = getchar();
  }
  if (ch == '-')
    minus = true;
  else
    result = ch - '0';
  while (1) {
    ch = getchar();
    if (ch < '0' || ch > '9') break;
    result = result * 10 + (ch - '0');
  }
  if (minus)
    return -result;
  else
    return result;
}
const int MAX = 2e5 + 10;
unsigned char v[MAX];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n = read_int();
  for (int i = 0; i < n; i++) v[i] = read_int();
  int q = read_int();
  while (q--) {
    int l = read_int(), r = read_int();
    unsigned char x = read_int(), y = read_int();
    l--, r--;
    for (int i = l; i <= r; i++) v[i] = v[i] == x ? y : v[i];
  }
  for (int i = 0; i < n; i++) cout << int(v[i]) << " ";
  cout << '\n';
  exit(0);
}
