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
| Input | Output |
|---|---|
5 1 2 2 3 4 3 1 5 5 1 2 4 2 5 3 4 5 2 | 1 5 2 3 4 |
