Description

You and Xiaohua are playing a number guessing game with paper cups.
Xiaohua has placed $n$ paper cups upside down on the table, numbered from $1$ to $n$. Each cup has a number written inside.
Xiaohua first tells Xiaoming the numbers on each cup, then quickly performs $m$ swap operations:
Choose two cups $u$ and $v$, and swap their positions. (If $u$ and $v$ are the same, no swap occurs)
Now Xiaohua wants you to answer: what are the numbers on the cups after $m$ operations?

Input Format

The first line contains two numbers $n$ and $m$, representing the number of cups and operations ($1≤n,m≤50000$);
The second line contains $n$ numbers, representing the numbers inside each cup;
The next $m$ lines each contain two numbers $u$ and $v$, indicating which cups to swap.

Output Format

Output one line containing $n$ numbers, representing the numbers inside each cup after all swaps, separated by spaces.

Sample

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

1 3 5 20 11 4 7 6