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

Discussion

Statistics


56% Solution Ratio

MamnoonSiamEarliest, Apr '20

jahid_hasan17Fastest, 0.1s

riyad000Lightest, 823 kB

hamtydamtyShortest, 350B

Submit

Login to submit

Editorial

At first divide the array into sqrt(n) blocks, where each block contains sqrt(n) elements. This tric...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.