Car Workshops

In Byteland (Bajtocja) there is only one road connecting the east with the west. It passes through exactly $m$ cities, and in each of them there is a car workshop that can repaint a car. Every workshop runs a promotion under which it repaints a car of color $a_j$ into color $b_j$ for free (here $j$ is the number of the city along the road, $j = 1, 2, \dots, m$). Each workshop chooses these two colors independently, and every workshop has exactly one such promotion.

A convoy of $n$ cars set off from the east toward the west. The drivers in Byteland are very frugal, but they also like to freshen up their cars. For this reason every driver tries to repaint their car in each successive city, but does so only when it is free. In other words, at a given workshop a car is changed to color $b_j$ only if its current color is exactly $a_j$.

Knowing the initial colors of all the cars, determine their colors after they reach the west. Assume the road is one-way, that is, the cars move only from east to west.

The first line contains three integers $n$, $m$, and $k$ ($1 \le n, m, k \le 1\,000\,000$) separated by single spaces, denoting respectively the number of cars, the number of cities, and the number of possible car colors. The colors are numbered from $1$ to $k$.

The second line contains $n$ integers $k_i$ ($1 \le k_i \le k$) separated by single spaces, denoting the initial colors of the successive cars.

Each of the next $m$ lines describes the workshops visited in order along the route. Each such description consists of two integers $a_j$ and $b_j$ ($1 \le a_j, b_j \le k$) separated by a single space, meaning that the workshop in the $j$-th city repaints a car of color $a_j$ into color $b_j$ for free.

In the first and only line print $n$ integers, separated by single spaces, denoting the colors of the successive cars after they reach the west.

Walkthrough of the sample. At the first workshop the second and fifth cars (color $2$) are repainted, so the sequence of colors becomes 1 4 3 4 4. At the second workshop only the first car (color $1$) changes, giving 2 4 3 4 4. Finally, at the third workshop the second, fourth, and fifth cars (color $4$) are repainted, so the final sequence of colors is 2 1 3 1 1.