You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

众所周知，量子计算机有超导量子计算机、离子阱量子计算机、光量子计算机等类型。小仓鼠李华在“幼雾实验”课上发现了一种新的粒子，其自旋量子数为 2。李华将其命名为“小仓鼠玻色子”（简称“仓鼠子”），它认为基于该粒子有望设计一种全新的量子计算机——仓鼠子量子计算机。

李华将 $n$ 个仓鼠子排成一列，并人为鼠为地为它们编号 $1 \sim n$。该粒子具有独特的纠缠特性，因此可以很方便地对区间 $[l_i,r_i]$ 的仓鼠子进行一次“比特翻转”操作，即将序列中第 $l_i \sim r_i$ 个仓鼠子顺序逆转。由于量子计算机的设计需要，一轮比特翻转操作需要对 $m$ 个区间 $[l_1,r_1],...,[l_m,r_m]$ 依次各进行一次比特翻转操作。

由于进行实际实验需要耗费大量的时间和财力，李华希望你能帮忙写个模拟程序，给出 $k$ 轮比特翻转操作后这列仓鼠子的编号序列。

Input

输入第一行： 3 个整数 $n, m, k$（$1 \le n \le 10^5, 1 \le m \le 100, 1 \le k \le 10^9$），表示仓鼠子的数量、区间的数量和比特翻转的轮数。

接下来 $m$ 行：每行两个整数 $l_i, r_i$（$1 \le l_i lt.eq r_i \le n$），表示区间。

Output

输出一行：$n$ 个整数，表示操作完成后仓鼠子的编号序列。

Examples

Sample Input 1

7 2 2
2 5
3 7

Sample Output 1

1 2 4 3 5 7 6

样例中，初始编号序列为 1 2 3 4 5 6 7。

第一轮比特翻转操作：第一次翻转 $[2, 5]$，编号序列变为 1 5 4 3 2 6 7；第二次翻转 $[3, 7]$，编号序列变为 1 5 7 6 2 3 4。

第二轮比特翻转操作：第一次翻转 $[2, 5]$，编号序列变为 1 2 6 7 5 3 4；第二次翻转 $[3, 7]$，编号序列变为 1 2 4 3 5 7 6。