Description

一天 jbgg 被磊神赶出了实验室。第二天 jbgg 想进入实验室的时候发现门的密码被磊神修改了，幸运的是博爱的磊神给 jbgg 留下了一张纸条，上面有一个数字串和一张数字转换表，只要 jbgg 能获取密码就能再次进入实验室。

一个数字串由 $n$ 个正整数 $x_1, x_2, \cdots, x_n$ 组成。

转换表有 $m$ 行，每行一个转换组，每个转换组的形式为 $a \to b$，表示数字 $a$ 转换成数字 $b$，如：$3 \to 4$。

jbgg 猜到只要将数字串中出现在转换表中的所有数字按照转换表进行连续转换，直至无法再次转换后得到的数字串便是最终密码。但磊神给的数字串太长了，jbgg 无法完成所有转换，你能写一个程序帮助 jbgg 完成转换吗？

Format

Input

第一行两个正整数 $n,\ m\ (1\le n \le 10^5,\ 1 \le m \le 10^3)$，分别表示要解密的数字串长度和转换表的行数。

接下来一行有 $n$ 个用空格分隔的正整数 $x_1,x_2,\cdots,x_n\ (1 \le x_i \le 10^5)$，表示待解密的数字串。

接下来 $m$ 行，每行两个正整数 $a,\ b\ (1 \le a,b \le 10^5)$，表示从 $a$ 转换到 $b$，保证每种转换仅出现一次。

数据保证不会出现一个数字可以转换成多个数字以及一个经过连续转换后会变回自身的情况。

Output

输出一行 $n$ 个正整数，数字之间用空格隔开。

Samples

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

5 5 5 5 5

18 16
1 2 3 4 5 6 7 8 233 9 10 3 5 11 12 13 14 15
15 48
14 53
1 67
12 77
6 84
11 86
3 97
10 100
13 101
7 104
2 114
233 2
9 115
8 117
5 121
4 122

67 114 97 122 121 84 104 117 114 115 100 97 121 86 77 101 53 48 

Notes

第一个样例的连续转换如下：

数字串 $1,2,3,4,5$ 中的每个数字在经过连续转换后变成 $5,5,5,5,5$。

Limitation

1s, 1024KiB for each test case.