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 target("sse2")
const int MAX = 1000010;
const long long MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LLINF = 0x3f3f3f3f3f3f3f3f;
const long double EPS = 1e-6;
const long double PI = acos(-1.0);
using namespace std;
int main() {
  int n, q, l, r;
  unsigned char a[200010], x, y;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%hhu", &a[i]);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &l, &r);
    scanf("%hhu%hhu", &x, &y);
    for (int i = l - 1; i < r; i++)
      if (a[i] == x) a[i] = y;
  }
  for (int i = 0; i < n; i++) printf("%hhu ", a[i]);
  printf("\n");
  return 0;
}
