N개의 정수로 이루어진 배열이 주어집니다. 이후 총 Q개의 질문이 주어지는데, 각 질문은 배열의 두 인덱스 a와 b를 의미합니다.

질문을 받을 때마다 a번째 원소와 b번째 원소의 위치를 서로 바꾸어야 합니다.

Q개의 모든 질문을 수행한 뒤, 최종적으로 변경된 배열의 상태를 출력하는 프로그램을 작성하시오.

(배열의 인덱스는 1번부터 N번까지 번호가 매겨집니다.)

입력

첫째 줄에 배열의 크기 N과 질문의 개수 Q가 공백을 사이에 두고 주어진다.

둘째 줄에 N개의 배열 원소가 공백을 사이에 두고 주어진다.

셋째 줄부터 Q개의 줄에 걸쳐 바꾸고자 하는 두 원소의 위치 a와 b가 공백을 사이에 두고 주어진다.

출력

모든 스왑(Swap) 연산이 끝난 후, 최종 배열의 원소들을 첫째 줄에 공백으로 구분하여 출력한다.

제한 사항

• 2 ≤ N ≤ 100,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ a, b ≤ N (a와 b가 같을 수도 있습니다.)
• 배열의 각 원소는 -1,000,000,000 이상 1,000,000,000 이하의 정수입니다.

예제 입력 1

5 3
10 20 30 40 50
1 3
4 2
3 5

예제 출력 1

30 40 50 20 10