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

题目背景

动物园里有 $n$ 只奶龙，它们身上分别乱序贴着编号 $1$ 到 $n$ ，管理员打算和它们玩一个“换位置”游戏。

题目描述

管理员预先准备了 $q$ 条交换指令，每条指令形如“第 $x$ 只奶龙和第 $y$ 只奶龙交换位置”。然后，管理员会重复执行这 $q$ 条指令一共 $m$ 轮（总计进行 $mq$ 次交换）。 游戏结束后，奶龙们的顺序会变成什么样呢？ 请你帮助园长输出最终它们的排列情况。

输入格式

第一行输入三个整数 $n, q, m$ ，分别代表园中奶龙的数量、指令操作的次数和进行的轮次。

第二行输入一个长度为 $n$ 的数组 $a_1 , a_2, \ldots, a_n$，代表奶龙们交换前的编号。

接下来 $q$ 行，每行输入两个整数 $l, r$ , 代表要交换的数字的位置。

输出格式

输出一个长度为 $n$ 的数组 $b_1, b_2, \ldots, b_n$，代表奶龙们交换后的编号。

样例 #1

样例输入 #1

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

样例输出 #1

6 1 10 2 5 3 9 4 8 7 

提示

对于 $30\%$ 数据，满足 $1 \leq n , m , q \leq 10^3$ 。

对于 $50\%$ 数据，满足 $1 \leq n \leq 10^3$ , $1 \leq m,q \leq 10^5$ 。

对于 $100\%$ 数据，满足 $1 \leq n, q \leq 10^5$ , $1 \leq m \leq 10^9$ , $1 \leq l , r \leq n$ 。