Farmer John 的 $N$ 头奶牛（$1\le N\le 10^5$）排成一行。对于每个 $1\le i\le N$，从左数第 $i$ 头奶牛的编号为 $i$。

Farmer John 为奶牛设计了新的晨练。他给出 $M$ 对整数 $(L_1,R_1) \ldots (L_M, R_M)$，其中 $1 \leq M \leq 100$，要求奶牛将以下 $M$ 步过程恰好重复 $K$（$1\le K\le 10^9$）次：

• 对于每个从 $1$ 到 $M$ 的 $i$：
• 当前从左数位于 $L_i \ldots R_i$ 的奶牛序列将顺序反转。

重复该过程恰好 $K$ 次后，对于每个 $1\le i\le N$，输出从左数第 $i$ 头奶牛的编号。

输入格式

第一行包含 $N$、$M$ 和 $K$。对于每个 $1\le i\le 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\le 10^3$。
• 测试用例 6-10 没有额外约束。

题目作者：Brian Dean