자동차 정비소

바이트나라(Bajtocja)에는 동쪽과 서쪽을 잇는 도로가 단 하나 있습니다. 이 도로는 정확히 $m$개의 도시를 지나가며, 각 도시에는 자동차를 다시 칠해 주는 정비소가 하나씩 있습니다. 각 정비소는 색 $a_j$인 자동차를 색 $b_j$로 무료로 도색해 주는 이벤트를 진행합니다(여기서 $j$는 도로를 따라가는 도시의 번호로, $j = 1, 2, \dots, m$입니다). 두 색 $a_j$, $b_j$는 정비소마다 서로 독립적으로 정하며, 각 정비소에는 이러한 이벤트가 정확히 하나씩 있습니다.

동쪽에서 서쪽으로 $n$대의 자동차로 이루어진 행렬이 출발했습니다. 바이트나라의 운전자들은 매우 알뜰하지만 동시에 자기 차를 새롭게 단장하는 것도 좋아합니다. 그래서 모든 운전자는 지나가는 도시마다 차를 다시 칠하려 하지만, 무료일 때에만 실제로 도색합니다. 즉 어떤 정비소에서 현재 자기 차의 색이 정확히 $a_j$일 때에만 그 차를 색 $b_j$로 바꿉니다.

모든 자동차의 처음 색을 알고 있을 때, 이 자동차들이 서쪽에 도착한 뒤의 색을 구하세요. 도로는 일방통행이므로 자동차는 동쪽에서 서쪽 방향으로만 이동한다고 가정합니다.

첫째 줄에 세 정수 $n$, $m$, $k$ ($1 \le n, m, k \le 1\,000\,000$)가 하나의 공백으로 구분되어 주어집니다. 각각 자동차의 수, 도시의 수, 자동차가 가질 수 있는 색의 수를 의미합니다. 색은 $1$번부터 $k$번까지 번호가 매겨져 있습니다.

둘째 줄에는 $n$개의 정수 $k_i$ ($1 \le k_i \le k$)가 하나의 공백으로 구분되어 주어지며, 앞에서부터 각 자동차의 처음 색을 의미합니다.

이어지는 $m$개의 줄에는 도로를 따라 차례로 방문하는 정비소의 정보가 주어집니다. 각 줄은 하나의 공백으로 구분된 두 정수 $a_j$, $b_j$ ($1 \le a_j, b_j \le k$)로 이루어지며, $j$번째 도시의 정비소가 색 $a_j$인 자동차를 색 $b_j$로 무료로 도색한다는 뜻입니다.

첫째 줄에 $n$개의 정수를 하나의 공백으로 구분하여 출력하세요. 앞에서부터 각 자동차가 서쪽에 도착한 뒤의 색을 의미합니다.

샘플이 처리되는 과정은 다음과 같습니다. 첫 번째 정비소에서는 색이 $2$인 두 번째와 다섯 번째 자동차가 도색되어 색의 순서가 1 4 3 4 4가 됩니다. 두 번째 정비소에서는 색이 $1$인 첫 번째 자동차만 바뀌어 2 4 3 4 4가 됩니다. 마지막 세 번째 정비소에서는 색이 $4$인 두 번째, 네 번째, 다섯 번째 자동차가 도색되어 최종 색의 순서는 2 1 3 1 1이 됩니다.