Để tối ưu hóa thuật toán đề xuất bài viết cho phần mềm SetNews, cô Mẫn và team phát triển đang phải đau đầu giải quyết một bài toán tổ hợp cốt lõi mang tên "Hoán vị đẹp".

Trong bài toán này, một hoán vị \(P\) của tập hợp các số nguyên từ \(1\) đến \(n\) được gọi là "đẹp" nếu nó có đúng \(m\) cặp nghịch thế. Một cặp nghịch thế (inversion) là một cặp chỉ số \((i, j)\) thỏa mãn \(1 \le i < j \le n\) và \(P_i > P_j\).

Ví dụ, hoán vị \(P = (1, 4, 2, 3)\) có đúng 2 cặp nghịch thế là \((2, 3)\) vì \(P_2 > P_3\) (tức \(4 > 2\)), và \((2, 4)\) vì \(P_2 > P_4\) (tức \(4 > 3\)).

Team SetNews cần tạo ra một danh sách chứa tất cả các hoán vị đẹp có thể có, sau đó sắp xếp danh sách này theo thứ tự từ điển tăng dần. Để kiểm tra tính đúng đắn của hệ thống, cô Mẫn cần trích xuất ra hoán vị nằm ở vị trí thứ \(k\) trong danh sách.

Yêu cầu: Cho ba số nguyên \(n, m, k\). Hãy tìm hoán vị đứng thứ \(k\) trong danh sách các hoán vị đẹp đã được sắp xếp. Do \(n\) có thể rất lớn, bạn không cần in ra toàn bộ hoán vị mà chỉ cần in ra số lượng và chi tiết các vị trí bị xáo trộn (tức là các vị trí \(i\) mà \(P_i \neq i\)). Nếu số lượng hoán vị đẹp thỏa mãn ít hơn \(k\), hãy in ra -1.

Input

• Một dòng duy nhất chứa ba số nguyên \(n, m\) và \(k\) cách nhau bởi khoảng trắng.
• Ràng buộc: \(1 \le n \le 10^{18}\); \(0 \le m \le 200\); \(1 \le k \le 10^{18}\).

Output

• Nếu không tồn tại hoán vị thứ \(k\), in ra -1.
• Nếu tồn tại:
  • Dòng đầu tiên in ra một số nguyên \(S\) là số lượng vị trí bị thay đổi (số lượng chỉ số \(i\) mà \(P_i \neq i\)).
  • \(S\) dòng tiếp theo, mỗi dòng in ra hai số nguyên \(i\) và \(P_i\) cách nhau một khoảng trắng, thể hiện giá trị tại vị trí \(i\) của hoán vị. Yêu cầu in các dòng này theo thứ tự chỉ số \(i\) tăng dần.
  • Dữ liệu vào đảm bảo \(S \le 10^5\)

Example

4 2 2

3
2 4
3 2
4 3

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n \le 10\); \(k \le 10^5\)
• Subtask 2 (\(30\%\) số điểm): \(n \le 1000\); \(k \le 10^9\)
• Subtask 3 (\(20\%\) số điểm): \(n \le 10^{18}\); \(k \le 10^6\)
• Subtask 4 (\(30\%\) số điểm): Không có ràng buộc gì thêm.