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

Farmer John đã nghĩ ra một bài tập thể dục buổi sáng mới cho đàn bò. Ông đưa cho đàn bò \(M\) cặp số nguyên \((L_1,R_1),\ldots,(L_M,R_M)\), trong đó \(1\leq M\leq 100\). Sau đó, ông yêu cầu chúng lặp lại chính xác \(K\) lần (\(1\le K\le 10^9\)) quy trình gồm \(M\) bước sau:

• Với mỗi \(i\) từ \(1\) đến \(M\):
  • Dãy bò hiện đang ở các vị trí \(L_i\ldots R_i\) tính từ bên trái đảo ngược thứ tự.

Sau khi đàn bò đã lặp lại quy trình này đúng \(K\) lần, với mỗi \(1\le i\le N\), hãy in nhãn của con bò thứ \(i\) tính từ bên trái.

Phân nhóm

• Test 2 thỏa mãn \(N=K=100\).
• Các test 3-5 thỏa mãn \(K\le 10^3\).
• Các test 6-10 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(K\). Với mỗi \(1\le i\le M\), dòng thứ \(i+1\) chứa \(L_i\) và \(R_i\), là hai số nguyên thuộc đoạn \(1\ldots N\) và thỏa mãn \(L_i<R_i\).

Dữ liệu ra

Trên dòng thứ \(i\) của kết quả, in phần tử thứ \(i\) của mảng sau khi dãy chỉ dẫn đã được thực hiện \(K\) lần.

Ví dụ

7 2 2
2 5
3 7

1
2
4
3
5
7
6

Nguồn

USACO 2020 February Contest, Silver - Swapity Swapity Swap: https://usaco.org/index.php?page=viewproblem2&cpid=1014

Tác giả: Brian Dean.