$N$ con bò của Farmer John ($1\le N\le 10^5$) đứng thành hàng. Với mỗi $1\le i\le N$, bò thứ $i$ từ trái có nhãn $i$.

Farmer John nghĩ ra bài tập sáng mới. Ông cho đàn bò $M$ cặp số nguyên $(L_1,R_1) \ldots (L_M, R_M)$, với $1 \leq M \leq 100$, và yêu cầu lặp lại quy trình $M$ bước sau đúng $K$ lần ($1\le K\le 10^9$):

• Với mỗi $i$ từ $1$ đến $M$:
• Các con bò hiện ở vị trí $L_i \ldots R_i$ từ trái đảo ngược thứ tự.

Sau đúng $K$ lần lặp, in nhãn bò thứ $i$ từ trái với mỗi $1\le i\le N$.

Dữ liệu vào

Dòng đầu chứa $N$, $M$ và $K$. Với mỗi $1\le i\le M$, dòng $i+1$ chứa $L_i$ và $R_i$, đều là số nguyên trong $1 \ldots N$, với $L_i < R_i$.

Dữ liệu ra

Ở dòng thứ $i$, in phần tử thứ $i$ của mảng sau khi chuỗi chỉ dẫn được thực hiện $K$ lần.

Ví dụ

Dữ liệu vào 1

7 2 2
2 5
3 7

Dữ liệu ra 1

1
2
4
3
5
7
6

Ghi chú

Ban đầu thứ tự từ trái là $[1,2,3,4,5,6,7]$. Sau bước đầu là $[1,5,4,3,2,6,7]$, sau bước hai là $[1,5,7,6,2,3,4]$. Lặp lại cả hai bước lần thứ hai cho kết quả ví dụ.

Nhiệm vụ con

• Bộ kiểm tra 2 thỏa mãn $N=K=100$.
• Các bộ kiểm tra 3-5 thỏa mãn $K\le 10^3$.
• Các bộ kiểm tra 6-10 không có ràng buộc bổ sung.

Tác giả bài toán: Brian Dean