[USACO20FEB] Swapity Swapity Swap S
题目描述
Farmer John 的 $N$ 头奶牛($1\leq N\leq 10^5$)站成一排。对于每一个 $1\leq i\leq N$,从左往右数第 $i$ 头奶牛的编号为 $i$。
Farmer John 想到了一个新的奶牛晨练方案。他给奶牛们 $M$ 对整数 $(L_1,R_1)\ldots (L_M,R_M)$,其中 $1\leq M\leq 100$。他让她们重复以下包含 $M$ 个步骤的过程 $K$($1\leq K\leq 10^9$)次:
对于从 $1$ 到 $M$ 的每一个 $i$:
- 当前从左往右数在位置 $L_i\ldots R_i$ 的奶牛序列反转她们的顺序。
- 当奶牛们重复这一过程 $K$ 次后,请对每一个 $1\leq i\leq N$ 输出从左往右数第 $i$ 头奶牛的编号。
输入输出格式
输入格式
输入的第一行包含 $N$,$M$ 和 $K$。对于每一个 $1\leq i\leq M$,第 $i+1$ 行包含 $L_i$ 和 $R_i$,均为范围在 $1\ldots N$ 内的整数,其中 $L_i<R_i$。
输出格式
在第 $i$ 行输出指令序列执行了 $K$ 次后奶牛序列中从左往右数第 $i$ 个元素的编号。
输入输出样例
输入样例 #1
7 2 2
2 5
3 7
输出样例 #1
1
2
4
3
5
7
6
说明
#### 样例解释:
初始时,奶牛们的顺序从左往右为 [$1,2,3,4,5,6,7$]。在这一过程的第一步过后,顺序变为 [$1,5,4,3,2,6,7$]。在这一过程的第二步过后,顺序变为 [$1,5,7,6,2,3,4$]。再重复这两个步骤各一次可以得到样例的输出。
#### 子任务:
- 测试点 $2$ 满足 $N=K=100$。
- 测试点 $3$-$5$ 满足 $K\leq 10^3$。
- 测试点 $6$-$10$ 没有额外限制。