G. Запросы на массовое обновление
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив a, состоящий из n целых чисел. Вам необходимо обработать q запросов к этому массиву; каждый запрос задается четверкой чисел l, r, x и y, означающих, что для каждого i такого, что l ≤ i ≤ r и ai = x необходимо установить ai равным y.

Выведите массив после обработки всех запросов.

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 200000) — размер массива a.

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 100) — элементы массива a.

В третьей строке записано одно целое число q (1 ≤ q ≤ 200000) — количество запросов, которые требуется обработать.

Затем следуют q строк. В i-й из них записаны четыре целых числа l, r, x и y, определяющие i-й запрос (1 ≤ l ≤ r ≤ n, 1 ≤ x, y ≤ 100).

Выходные данные

Выведите n целых чисел — элементы массива a после применения всех операций.

Пример
Входные данные
5
1 2 3 4 5
3
3 5 3 5
1 5 5 1
1 5 1 5
Выходные данные
5 2 5 4 5