题目描述

自从徐老师派机器人去羊腿店接单以来，收到了不少的差评

因为机器人永远只会同时制作一份订单，速度过慢

于是徐老师给机器人手臂增加了一个变幻功能，使得机器人可以瞬间变化出一堆手臂，同时操作很多羊腿

也就是说现在机器人可以把 $n$ 只羊腿排成一排同时烤，为了方便，我们给这些羊腿从左往右依次编号为 $1 \sim n$

而现在，由于烤羊腿的火力要求不同，机器人需要每隔一段时间将一部分羊腿交换位置，使得它们烤制的火力强度不同

而由于徐老师只是给手臂增加了变幻功能，所以每次机器人只能将连续的一段羊腿进行翻转

比如一开始有 $5$ 只羊腿，编号分别为 $[1,2,3,4,5]$

机器人第一次翻转区间 $[2,4]$ 的羊腿，翻转后变成 $[1,4,3,2,5]$

机器人第二次翻转区间 $[3,5]$ 的羊腿，翻转后变成 $[1,4,5,2,3]$

机器人第三次翻转区间 $[1,4]$ 的羊腿，翻转后变成 $[2,5,4,1,3]$

最终烧烤台上的羊腿编号分别为 $[2,5,4,1,3]$

现在徐老师已经给机器人下达了所有的烤制步骤——一共 $m$ 次翻转

但是徐老师居然忘记给机器人下达终止命令！导致机器人并没有在做完 $m$ 次翻转后停止操作，而是继续从第一次翻转操作开始循环执行这些命令

当徐老师发现这个问题时，发现机器人已经完成了正好 $k$ 轮烤制操作（每轮会依次执行 $m$ 次翻转操作）

现在徐老师马上就要交付订单了，他需要知道每个编号的羊腿分别在什么位置

输入格式

第一行包含三个整数 $n,m,k$，含义如题

接下来 $m$ 行，每行包含两个整数 $x_i,y_i$，表示第 $i$ 步翻转的烤制操作是将当前的第 $x_i \sim y_i$ 这段羊腿进行翻转

输出格式

输出一行包含 $n$ 个整数，依次表示每个编号的羊腿最终在哪个位置

数据范围

对于 $20\%$ 的数据满足 $2\le n \le 100, 0\le k \le 100$；

对于 $50\%$ 的数据满足 $0\le k \le 1000$；

对于 $100\%$ 的数据满足 $2\le n \le 100000, 1\le m \le 100, 0\le k \le 10^9$。

样例输入1

5 3 1
2 4
3 5
1 4

样例输出1

4 1 5 3 2

样例解释1

进行完所有操作后，烧烤台上的羊腿依次为 $[2,5,4,1,3]$

所以 $1$ 号所在位置为 $4$ 所以 $2$ 号所在位置为 $1$ 所以 $3$ 号所在位置为 $5$ 所以 $4$ 号所在位置为 $3$ 所以 $5$ 号所在位置为 $2$

样例输入2

7 2 2
2 5
3 7

样例输出2

1 2 4 3 5 7 6