Nhiệm vụ của bạn là chọn $N$ điểm trên mặt phẳng tọa độ và vẽ $M$ đoạn thẳng nối chúng sao cho có đúng $K$ mặt hữu hạn. Ở đây, các mặt là những vùng mà mặt phẳng bị chia cắt bởi các đoạn thẳng. Một trong các vùng là vô hạn và cần được bỏ qua.

Cụ thể hơn, cấu hình của bạn phải thỏa mãn các điều kiện sau:

• Tọa độ $x$ và $y$ của mỗi điểm phải là các số nguyên từ 1 đến 79.
• Tất cả các điểm phải có vị trí khác nhau.
• Không được có nhiều đoạn thẳng nối hai điểm.
• Hai đoạn thẳng khác nhau không được cắt nhau ngoại trừ tại một điểm đầu mút.
• Các điểm khác ngoài hai điểm đầu mút của đoạn thẳng không được nằm trên đoạn thẳng đó.

Trong hình dưới đây, (a) là trường hợp tạo ra một mặt với 3 điểm và 3 đoạn thẳng. (b) là trường hợp tạo ra 3 mặt với 4 điểm và 6 đoạn thẳng. (c) là kết quả không hợp lệ vì có các đường cong, và (d) là không hợp lệ vì có các đoạn thẳng cắt nhau.

Dữ liệu vào

Trên dòng đầu tiên, có ba số nguyên dương $N, M$ và $K$, lần lượt biểu thị số lượng điểm, số lượng đoạn thẳng và số lượng mặt cần tạo ra ($3 \le N \le 3000, 0 \le M, 0 \le K$).

Đảm bảo rằng với $N, M$ và $K$ đã cho, luôn tồn tại một lời giải.

Dữ liệu ra

Trên $N$ dòng đầu tiên, in tọa độ của các điểm đã chọn. Dòng thứ $i$ trong số đó phải chứa hai số nguyên $x_i$ và $y_i$ ($1 \le x_i, y_i \le 79$): tọa độ của điểm thứ $i$.

Sau đó in $M$ dòng mô tả các đoạn thẳng. Mỗi dòng trong số này phải chứa hai số nguyên từ 1 đến $N$: chỉ số của các điểm được nối bởi một đoạn thẳng.

Nếu có nhiều hơn một lời giải khả thi, hãy in bất kỳ lời giải nào trong số đó.

Ví dụ

Ví dụ 1

4 6 3

1 1
3 1
2 2
2 3
1 2
1 3
1 4
2 3
2 4
3 4

Ví dụ 2

6 5 1

1 1
1 2
2 1
3 1
3 2
4 1
1 2
1 3
2 3
4 5
5 6

Ghi chú

Hình bên trái cho thấy 3 mặt được tạo bởi 4 điểm và 6 đoạn thẳng. Hình bên phải cho thấy 1 mặt được tạo bởi 6 điểm và 5 đoạn thẳng.