You are given an array a consisting of $n$ integers. You have to process $q$ queries to this array; each query is given as four numbers $l$, $r$, $x$ and $y$, denoting that for every $i$ such that $l ≤ i ≤ r$ and $a_i = x$ you have to set $a_i$ equal to $y$.
Print the array after all queries are processed.
The first line contains one integer $n$ ($1 ≤ n ≤ 200000$) — the size of array $a$.
The second line contains $n$ integers $a_1, a_2, …, a_n$ ($1 ≤ a_i ≤ 100$) — the elements of array a.
The third line contains one integer $q$ ($1 ≤ q ≤ 200000$) — the number of queries you have to process.
Then $q$ lines follow. $i$-th line contains four integers $l$, $r$, $x$ and $y$ denoting $i$-th query ($1 ≤ l ≤ r ≤ n$, $1 ≤ x, y ≤ 100$).
Print $n$ integers — elements of array $a$ after all changes are made.
5 2 5 4 5