Bài 14.4. Đặt Vệ Binh Trên Bàn Cờ Cổ - [Độ khó: Khó]

Trong một vương quốc cổ đại, quân đội cần bố trí \(K\) vệ binh trên một bàn cờ hình vuông \(N \times N\) để bảo vệ cung điện. Quy tắc là không có hai vệ binh nào được phép tấn công lẫn nhau. Một vệ binh đặt tại ô \((r, c)\) tấn công bất kỳ ô nào nằm trên cùng hàng, cùng cột hoặc cùng đường chéo với nó (tương tự như quân Hậu trong cờ vua).

Bạn là một chiến lược gia tài ba. Nhiệm vụ của bạn là tìm một cách bố trí \(K\) vệ binh lên bàn cờ \(N \times N\) sao cho không có hai vệ binh nào tấn công nhau. Nếu có nhiều cách, bạn có thể đưa ra bất kỳ cách nào. Nếu không thể bố trí được, bạn phải thông báo.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le N \le 10\), \(1 \le K \le N\)).

OUTPUT FORMAT

Nếu có thể bố trí, in ra \(K\) dòng, mỗi dòng chứa hai số nguyên \(r\) và \(c\) (\(0 \le r, c < N\)) là tọa độ của một vệ binh. Thứ tự các vệ binh không quan trọng. Nếu không thể bố trí, in ra KHONG_THE.

Ví dụ 1:

Input:

4 2

Output:

0 0
1 2

Giải thích: Bàn cờ \(4 \times 4\), cần đặt 2 vệ binh. Nếu đặt vệ binh 1 tại \((0,0)\) và vệ binh 2 tại \((1,2)\):

• Chúng không cùng hàng: \(0 \ne 1\).
• Chúng không cùng cột: \(0 \ne 2\).
• Chúng không cùng đường chéo:
  • Đường chéo chính: \(0-0=0\), \(1-2=-1\). \(0 \ne -1\).
  • Đường chéo phụ: \(0+0=0\), \(1+2=3\). \(0 \ne 3\). Vậy, đây là một cách bố trí hợp lệ. Có thể có các cách bố trí hợp lệ khác.

Ví dụ 2:

Input:

2 2

Output:

KHONG_THE

Giải thích: Trên bàn cờ \(2 \times 2\), không thể đặt 2 vệ binh mà chúng không tấn công nhau. Nếu đặt vệ binh đầu tiên, ô thứ hai sẽ luôn bị nó tấn công. Ví dụ, đặt tại \((0,0)\), thì \((0,1)\), \((1,0)\) và \((1,1)\) đều bị tấn công.