Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

有一个长度为 $n$ 的整数数组 $a_0,a_1\cdots,a_{n-1}$,有一个长度为 $m$ 的操作序列 $(b_0,c_0),(b_1,c_1)\cdots (b_{m-1},c_{m-1})$。

执行 $t$ 次操作,第 $i$ 次操作(操作从 1 开始编号)执行:

$$ swap(a_{(b_{i\ \bmod\ m}+i)\bmod\ n},a_{(c_{i\ \bmod\ m}+i)\bmod\ n}) $$

问 $t$ 次操作后 $a$ 序列会变成什么样。

输入格式

第一行三个整数 $n,m,t$。

第二行 $n$ 个整数,表示数组 $a$。

接下来 $m$ 行每行两个整数 $b_i,c_i$,给出操作序列。

输出格式

一行 $n$ 个整数,用空格隔开,表示操作后的 $a$ 序列。

样例1

input

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

output

5 9 3 9 8 8 9 4 6 10

样例2

见下发文件。

下发样例

数据范围及约束

对于所有数据,保证 $0\leq b_i,c_i < n,1\leq a_i\leq n,b_i\neq c_i$

对于所有数据,有 $1\leq \ n,m\leq 10^5;\ t\leq 10^{10}$。

对于 10% 的数据:$t\leq 10^7$。

另有 20% 的数据: $n,m\leq 1000$

另有 10% 的数据:$m=1$

另有 10% 的数据:$m=n$

Hint:请仔细阅读题目中哪些标号是从 0 开始的哪些标号是从 1 开始的。

如果出事了联系ljy。