该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

本题大样例

题目背景：

什么，你要跟我换东西……

题目描述

我有 $n$ 件物品，第 $i$ 件物品的价格为 $a_i$。

你可以进行 $q$ 种操作，第 $i$ 种操作是将第 $x_i$ 件物品和第 $y_i$ 件物品的价格交换。

每种操作可以进行无限次。

但是跟我换东西，需要保证经过所有交换后的 $a`$ 序列是我最喜欢的，即不会存在别的交换后的序列 $a``$ 满足 $a``$ 的字典序大于 $a`$。

输入格式

第 $1$ 行，两个正整数 $n$ 和 $q$。

第 $2$ 行，共 $n$ 个正整数，第 $i$ 个数表示 $a_i$。

第 $3 \sim q+2$ 行，每行两个正整数 $x_i,y_i$。

输出格式

一行，共 $n$ 个正整数表示答案。

输入输出样例

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

5 4 3 2 1

10 3
1 5 4 3 2 4 2 8 4 6
1 3
3 4
2 3

5 4 3 1 2 4 2 8 4 6 

提示

数据规模与约定

对于 $100 \%$ 的数据， 保证 $a_i \leq 10^6$。