Đổi chỗ

Giới hạn thời gian: 1000 ms

Giới hạn bộ nhớ: 256 MB

Cho một mảng A gồm các số nguyên. Thực hiện lần lượt q thao tác đổi chỗ hai phần tử trong mảng A , ta thu được một mảng B mới. Cho mảng B , hãy khôi phục lại mảng A ban đầu.

Input

Dòng đầu tiên gồm hai số nguyên n , q . Dòng thứ hai gồm n số nguyên B i . q dòng tiếp theo, mỗi dòng gồm hai chỉ số x , y với 1 ≤ x , y ≤ n , thể hiện thao tác đổi chỗ hai phần tử ở vị trí x và y của mảng A .

Output

In ra n số nguyên là mảng A ban đầu. Ràng buộc 1 ≤ n , q , B i ≤ 1000 .

Ví dụ

Input:

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

Output:

4 3 5 2 1