题目描述

Farmer John 的 N头奶牛站成一排。

对于每一个 $1≤i≤N$，从左往右数第$i$头奶牛的编号为$i$。

Farmer John 想到了一个新的奶牛晨练方案。

他给奶牛们$M$对整数 $(L_1,R_1)…(L_M,R_M)$。

他让她们重复以下包含 $M$ 个步骤的过程$K$次：

对于从$1$到$M$的每一个$i$：

当前从左往右数在位置$L_i…R_i$的奶牛序列反转她们的顺序。

当奶牛们重复这一过程 $K$次后，请对每一个$1≤i≤N$ 输出从左往右数第$i$头奶牛的编号。

输入

输入的第一行包含 $N,M,K$。

对于每一个 $1≤i≤M$，第$i+1$ 行包含$L_i和 R_i$，均为范围在 $1…N$内的整数，其中$L_i<R_i$。

输出

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

样例输入

7 2 2
2 5
3 7

样例输出

1
2
4
3
5
7
6

提示

$1≤N≤10^5$,

$1≤M≤100$,

$1≤K≤10^9$

初始时，奶牛们的顺序从左往右为 [1,2,3,4,5,6,7]。

在这一过程的第一步过后，顺序变为 [1,5,4,3,2,6,7]。

在这一过程的第二步过后，顺序变为 [1,5,7,6,2,3,4]。

再重复这两个步骤各一次可以得到样例的输出。