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>
static inline int64_t min(int64_t length1, int64_t length2) {
  return (length1 < length2) ? length1 : length2;
}
static inline int64_t max(int64_t length1, int64_t length2) {
  return (length1 > length2) ? length1 : length2;
}
struct linked_list {
  int64_t data;
  struct linked_list *next;
  struct linked_list *end;
};
typedef struct linked_list *ll_ptr;
int64_t arr[200010], origNum, newNum;
int64_t length, sqrtLength, intervals[500], numIntervals, startQuery, endQuery;
struct linked_list commandQueues[500][110], extraSpace[500][10000];
int64_t numQueries;
int64_t numSpaceUsed[500];
ll_ptr getLL(int64_t commandQueue, int64_t data) {
  numSpaceUsed[commandQueue]++;
  if (numSpaceUsed[commandQueue] > 10000)
    fprintf(stderr, "ERROR: USED TOO MUCH SPACE\n"), exit(1);
  extraSpace[commandQueue][numSpaceUsed[commandQueue] - 1].data = data;
  extraSpace[commandQueue][numSpaceUsed[commandQueue] - 1].next =
      extraSpace[commandQueue][numSpaceUsed[commandQueue] - 1].end = NULL;
  return extraSpace[commandQueue] + (numSpaceUsed[commandQueue] - 1);
}
int64_t sqrt_(int64_t n) {
  int64_t beg = 0, end = n, mid;
  while (beg < end) {
    mid = (beg + end) / 2;
    if (mid * mid == n)
      return mid;
    else if (mid * mid < n)
      beg = mid + 1;
    else
      end = mid;
  }
  return beg;
}
int64_t findInterval(int64_t n) {
  int64_t beg = 0, end = numIntervals - 1, mid;
  while (beg <= end) {
    mid = (beg + end) / 2;
    if ((intervals[mid] <= n) && (n < intervals[mid + 1]))
      return mid;
    else if (n < intervals[mid])
      end = mid - 1;
    else
      beg = mid + 1;
  }
  fprintf(stderr, "ERROR IN BINARY SEARCH\n");
  exit(1);
}
void processCommandQueue(int64_t interval) {
  int64_t k, commands[110];
  int64_t j;
  ll_ptr storePtr;
  for (k = 0; k < 110; k++) commands[k] = -1;
  for (k = 0; k < 110; k++) {
    for (storePtr = commandQueues[interval][k].next; storePtr != NULL;
         storePtr = storePtr->next) {
      if (commands[storePtr->data] != -1) {
        fprintf(stderr,
                "%" PRId64 " has commands of both %" PRId64 " and %" PRId64,
                storePtr->data, commands[storePtr->data], k);
        exit(1);
      }
      commands[storePtr->data] = k;
    }
  }
  for (j = intervals[interval]; j < intervals[interval + 1]; j++) {
    if (commands[arr[j]] == -1)
      fprintf(stderr, "%" PRId64 " has no command\n", arr[j]), exit(1);
    arr[j] = commands[arr[j]];
  }
  numSpaceUsed[interval] = 0;
  for (k = 0; k < 110; k++)
    commandQueues[interval][k].next = commandQueues[interval][k].end =
        getLL(interval, k);
}
int main() {
  int64_t i, firstInterval, lastInterval, queueSize;
  int64_t l;
  int64_t k;
  ll_ptr storePtr;
  scanf("%" PRId64, &length);
  sqrtLength = sqrt_(length);
  intervals[0] = 0;
  while ((numIntervals == 0) || (intervals[numIntervals] < length)) {
    numIntervals++;
    intervals[numIntervals] = intervals[numIntervals - 1] + sqrtLength;
    intervals[numIntervals] = min(length, intervals[numIntervals]);
  }
  for (i = 0; i < numIntervals; i++)
    for (k = 0; k < 110; k++)
      commandQueues[i][k].next = commandQueues[i][k].end = getLL(i, k);
  for (i = 0; i < length; i++) scanf("%" PRId64, arr + i);
  scanf("%" PRId64, &numQueries);
  for (l = 0; l < numQueries; l++) {
    scanf("%" PRId64 " %" PRId64 " %" PRId64 " %" PRId64, &startQuery,
          &endQuery, &origNum, &newNum);
    if (origNum == newNum) continue;
    startQuery--, endQuery--;
    firstInterval = findInterval(startQuery),
    lastInterval = findInterval(endQuery);
    processCommandQueue(firstInterval);
    for (i = startQuery; i < min(endQuery, intervals[firstInterval + 1]); i++) {
      if (arr[i] == origNum) arr[i] = newNum;
    }
    processCommandQueue(lastInterval);
    for (i = max(startQuery, intervals[lastInterval]); i <= endQuery; i++) {
      if (arr[i] == origNum) arr[i] = newNum;
    }
    for (i = firstInterval + 1; i < lastInterval; i++) {
      if (commandQueues[i][newNum].end == NULL) {
        if (commandQueues[i][newNum].next != NULL) {
          fprintf(stderr, "ERROR: INTERVAL %li HAS NEXT BUT NOT END\n", newNum);
          exit(1);
        }
        commandQueues[i][newNum].next = commandQueues[i][origNum].next;
        commandQueues[i][newNum].end = commandQueues[i][origNum].end;
      } else if (commandQueues[i][origNum].end != NULL) {
        commandQueues[i][newNum].end->next = commandQueues[i][origNum].next;
        commandQueues[i][newNum].end = commandQueues[i][origNum].end;
      }
      commandQueues[i][origNum].next = commandQueues[i][origNum].end = NULL;
    }
  }
  for (i = 0; i < numIntervals; i++) processCommandQueue(i);
  for (i = 0; i < length; i++)
    printf("%" PRId64 "%c", arr[i], (i + 1 == length) ? '\n' : ' ');
  exit(0);
}
