#1382. [USACO20FEB] Swapity Swapity Swap S

[USACO20FEB] Swapity Swapity Swap S

题目描述

Farmer John 的 NN 头奶牛(1≤N≤1051\leq N\leq 10^5)站成一排。对于每一个 1≤i≤N1\leq i\leq N,从左往右数第 ii 头奶牛的编号为 ii。

Farmer John 想到了一个新的奶牛晨练方案。他给奶牛们 MM 对整数 (L1,R1)…(LM,RM)(L_1,R_1)\ldots (L_M,R_M),其中 1≤M≤1001\leq M\leq 100。他让她们重复以下包含 MM 个步骤的过程 KK(1≤K≤1091\leq K\leq 10^9)次:

对于从 11 到 MM 的每一个 ii:

  • 当前从左往右数在位置 Li…RiL_i\ldots R_i 的奶牛序列反转她们的顺序。
  • 当奶牛们重复这一过程 KK 次后,请对每一个 1≤i≤N1\leq i\leq N 输出从左往右数第 ii 头奶牛的编号。

输入格式

输入的第一行包含 NN,MM 和 KK。对于每一个 1≤i≤M1\leq i\leq M,第 i+1i+1 行包含 LiL_i 和 RiR_i,均为范围在 1…N1\ldots N 内的整数,其中 $L_i

输出格式

在第 ii 行输出指令序列执行了 KK 次后奶牛序列中从左往右数第 ii 个元素的编号。

样例

7 2 2
2 5
3 7
1
2
4
3
5
7
6

题目来源:洛谷 P6148