Farmer John 的 N 头奶牛（1≤N≤10$^5$）站成一排。对于每一个 1≤i≤N，从左往右数第i 头奶牛的编号为 i。Farmer John 想到了一个新的奶牛晨练方案。他给奶牛们 M 对整数 (L$_1$,R$_1$)…(L$_M$,R$_M$)，其中 1≤M≤100。他让她们重复以下包含M 个步骤的过程 K（1≤K≤10$^9$）次：

• 对于从 1 到 M 的每一个 i：
• 当前从左往右数在位置L$_i$…R$_i$ 的奶牛序列反转她们的顺序。

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

测试点性质：

• 测试点 2 满足 N=K=100。
• 测试点 3-5 满足 K≤10$^3$。
• 测试点 6-10 没有额外限制。

输入格式（文件名：swap.in）：

输入的第一行包含 N, M 和K。对于每一个 1≤i≤M，第 i+1 行包含L$_i$ 和 R$_i$，均为范围在 1…N 内的整数，其中 L$_i$<R$_i$。

输出格式（文件名：swap.out）：

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

输入样例：

7 2 2
2 5
3 7

输出样例：

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]。再重复这两个步骤各一次可以得到样例的输出。