# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Change in Array

By tanu_RUET · Limits 3s, 1.0 GB

You will be given an array of length N. Then there will be Q queries. Each query will contain four integers, l r x y. For each query, you have to perform the following operation:

for (int i = l; i <= r; i++) {
if (array[i] == x) array[i] = y;
}


As this process is not efficient enough, you need to find a more optimized way to perform the task. After you are done with all the queries, print the array.

## Input

In the first line, there will be an integer N (1 ≤ N ≤ 105). The next line will contain N space-separated integers, the elements of the array initially (1 ≤ elements of array ≤ 104).

The next line will contain an integer Q (1 ≤ Q ≤ 105), the number of queries. Then each of the next Q lines each will contain four integers l r x y (1 ≤ x, y ≤ 104; 1 ≤ l ≤ r ≤ N), as described in the statement.

## Output

Print the elements of the final array after performing operations described by all the queries. Each element should be separated by a single space.

## Sample

InputOutput
5
1 2 2 3 4
3
1 5 5 1
2 4 2 5
3 4 5 2

1 5 2 3 4


• ### Statistics

56% Solution Ratio

MamnoonSiamEarliest, Apr '20

jahid_hasan17Fastest, 0.1s

hamtydamtyShortest, 350B

### Submit 