问题描述

你和小华正在玩纸杯猜数游戏。桌面上一排编号为 $1 \sim n$ 的 $n$ 个纸杯，每个纸杯内侧写有一个数字。小华先将这 $n$ 个数字告诉你，然后进行了 $m$ 次交换操作：每次选择两个纸杯 $u$ 和 $v$（若 $u=v$ 则不交换），交换它们的位置。现在请你回答：完成所有交换后，依次排列的纸杯内侧数字分别是多少？

输入格式

第一行输入两个整数 $n, m$，分别表示纸杯数和操作数，满足 $1 \le n, m \le 50000$；

第二行输入 $n$ 个整数，表示初始每个纸杯内侧的数字；

接下来 $m$ 行，每行两个整数 $u, v$，表示交换编号为 $u$ 和 $v$ 的纸杯。

输出格式

输出一行 $n$ 个整数，表示交换结束后依次排列的纸杯内侧数字，用空格分隔。

样例输入

8 3
1 4 7 20 5 3 11 6
3 7
2 6
5 3

样例输出

1 3 5 20 11 4 7 6