Change in Array

tanu_RUET BiE BAU Contest - 02
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

Submit

Login to submit.

Statistics

55% Solution Ratio
MamnoonSiamEarliest, Apr '20
jahid_hasan17Fastest, 0.1s
riyad000Lightest, 823 kB
hamtydamtyShortest, 350B
Toph uses cookies. By continuing you agree to our Cookie Policy.