Có \(n\) học sinh đang đứng xếp hàng trong sân trường, mỗi học sinh có một số thứ tự riêng biệt đánh số từ \(1\) tới \(n\). Cho biết trạng thái ban đầu của các em học sinh trong hàng, bạn cần thực hiện \(q\) thao tác. Mỗi thao tác sẽ bao gồm hai số \(i, j\) chính là số thứ tự của hai học sinh và bạn sẽ hoán đổi vị trí của họ. Bạn hãy in ra thứ tự của hàng sau khi thực hiện xong \(q\) thao tác.

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à số thứ tự các học sinh. Biết rằng \(1 \leq a[i] \leq n\) và không có hai học sinh nào có số thứ tự giống nhau.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i, j\) (\(1 \leq i, j \leq n, i \neq j\)) biểu thị thao tác hoán đổi vị trí của học sinh mang số \(i\) và học sinh mang số \(j\).

Output

• In ra \(n\) số là thứ tự sau cùng của các em học sinh.

Example

5 2
3 1 2 5 4
1 3
4 5

1 3 2 4 5