题目描述

X 有一个长为 $n$ 的正整数数列

X 会对这个数列做出 $q$ 次修改。第 $i$ 次修改有两个参数 $l_i,r_i$，X 会按顺序枚举

如果

则 X 会交换 $a_j$ 和 $a_{j+1}$ 的值。

Y 想知道在第 $i=1,2,\ldots,q$ 次修改后，

的值分别是多少。但是 X 并不想做奇奇怪怪的计算，因此 Y 只好求助于你。

对于一部分测试点，Y 并不想实时地知道 $s_i$，你只需要在所有修改后输出 $a$ 数组即可。对于这样的测试点有 $t=1$；对于那些需要计算 $s_i$ 的测试点有 $t=2$。

输入格式

第一行，三个正整数 $n,q,t$。

第二行，$n$ 个正整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行两个正整数 $l_i,r_i$。

输出格式

若 $t=1$：一行，$n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示所有修改后的 $a$ 数组。

若 $t=2$：一行，$q$ 个正整数 $s_1,s_2,\ldots,s_q$。

样例 1 输入

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

样例 1 输出

28 19 23 11 12 32

数据范围与子任务

对于所有数据：