Có \(n\) lá bài được đánh số từ \(1\) tới \(n\). Cho biết thứ tự ban đầu các lá bài trong bộ bài, bạn cần thực hiện \(q\) thao tác. Mỗi thao tác gồm hai số \(u, v\): hãy đổi vị trí của lá bài mang số \(u\) và lá bài mang số \(v\). Hãy in ra thứ tự các lá bài sau khi hoàn thành \(q\) thao tác.

Ví dụ, vị trí ban đầu các lá bài là \([1, 3, 2, 5, 4]\). Cần thực hiện hai thao tác \((1, 2)\) và \((2, 3)\).

• Sau thao tác \((1, 2)\), hai lá bài \(1\) và \(2\) bị tráo đổi vị trí. Vị trí các lá bài là \([2, 3, 1, 5, 4]\).
• Sau thao tác \((2, 3)\), hai lá bài \(2\) và \(3\) bị tráo. Thứ tự cuối cùng là \([3, 2, 1, 5, 4]\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q\) (\(1 \leq n, q \leq 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a[i]\) là thứ tự ban đầu các lá bài. Biết rằng \(1 \leq a[i] \leq n\) và không có hai số nào bằng nhau.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \leq u, v \leq n, u \neq v\)) biểu thị một thao tác.

Output

• In ra \(n\) số là thứ tự cuối cùng của các lá bài.

Example

5 2
1 3 2 5 4
1 2
2 3

3 2 1 5 4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 200\).
• Subtask \(2\) (\(30\%\) số điểm): \(n, q \leq 2000\).
• Subtask \(3\) (\(40\%\) số điểm): không có điều kiện gì thêm.