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]$、2 番目のステップ後は $[1,5,7,6,2,3,4]$ です。両ステップをもう一度行うと例の出力になります。

小課題

• テストケース 2 は $N=K=100$ を満たします。
• テストケース 3-5 は $K\le 10^3$ を満たします。
• テストケース 6-10 に追加の制約はありません。

問題作成：Brian Dean