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