주차 자리 교환 기록

문제

한 주차장에는 일렬로 놓인 N개의 주차 자리가 있다. 자리는 입구에서 가까운 순서대로 1번부터 N번까지 번호가 붙어 있다. 오늘 주차된 차량도 1번부터 N번까지 서로 다른 관리 번호를 받았다. 모든 자리에 차량이 정확히 한 대씩 있으며, 같은 차량이 두 자리에 나타나는 일은 없다. 주차장 관리자는 다음 날의 출차 준비를 위해 차량 배치를 조정한다. 조정 요청 하나에는 차량 번호와 그 차량을 놓아야 할 자리 번호가 적혀 있다. 요청을 처리할 때에는 먼저 해당 차량이 현재 어느 자리에 있는지 확인한다. 그런 다음 그 차량과 목적지 자리에 있는 차량의 자리를 서로 바꾼다. 따라서 요청을 처리한 뒤에도 모든 자리에는 차량이 정확히 한 대씩 있게 된다. 요청한 차량이 이미 목적지 자리에 있다면 아무 차량도 움직이지 않는다. 이 경우에도 요청 하나를 처리한 것으로 본다. 한 차량에 대한 요청이 여러 번 등장할 수 있고, 여러 요청이 같은 자리를 목적지로 지정할 수도 있다. 모든 요청은 입력된 순서대로 처리하며, 각 요청에서 말하는 현재 위치는 앞선 요청을 모두 반영한 위치이다. 관리 화면에는 처음 배치와 요청 목록만 남아 있다. 관리자는 이 기록을 이용해 모든 요청을 처리한 뒤의 배치를 복원하려 한다. 요청에 등장하지 않은 차량도 다른 차량과 자리를 바꾸면서 이동할 수 있으므로 처음 위치에 그대로 있다고 가정해서는 안 된다. 최종 배치는 자리 번호가 작은 순서대로 읽는다. 차량 번호가 작은 순서대로 위치를 나열하는 것이 아니라, 각 자리에 최종적으로 놓인 차량의 번호를 나열해야 한다. 요청이 하나도 없으면 처음 배치가 그대로 최종 배치가 된다. 주어진 처음 배치와 요청 목록으로 최종 차량 배치를 구한다.

입력

첫째 줄에 자리 수 N과 요청 수 M이 공백으로 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ M ≤ 20,000이다.
둘째 줄에 1번 자리부터 N번 자리까지 놓인 차량 번호가 공백으로 주어진다. 이 줄은 1부터 N까지의 정수가 한 번씩 나타나는 순열이다.
다음 M개 줄에 차량 번호 C와 목적지 자리 번호 P가 공백으로 주어진다. 1 ≤ C, P ≤ N이다.
입력에 등장하는 모든 수는 정수이다.

출력

모든 요청을 처리한 뒤 1번 자리부터 N번 자리까지 놓인 차량 번호를 공백으로 구분하여 한 줄에 출력한다.

4 3
2 4 1 3
1 1
4 4
2 2

1 2 3 4

3 2
3 1 2
1 2
3 3

2 1 3

1 0
1

1

출처: Devin.KR 자체 제작