Cho hai số nguyên \(n,k\). Hãy chọn \(n\) điểm nguyên phân biệt trên mặt phẳng \(xy\) sao cho có đúng \(k\) cặp điểm có khoảng cách Euclid là số nguyên. Khoảng cách giữa \((x_1,y_1)\) và \((x_2,y_2)\) là

Có thể chứng minh rằng luôn tồn tại lời giải với các ràng buộc của đề.

Dữ liệu vào

Dòng duy nhất chứa hai số nguyên \(n,k\).

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(i\) chứa hai số nguyên là tọa độ \(x,y\) của điểm thứ \(i\). Giá trị tuyệt đối của mọi tọa độ không được vượt quá \(10^9\).

Nếu có nhiều lời giải, có thể in bất kỳ lời giải hợp lệ nào.

Ràng buộc

• \(1\le n\le100\).
• \(0\le k\le n(n-1)/2\).

Phân nhóm

1. \(11\) điểm: \(n\le4\).
2. \(4\) điểm: \(k=n(n-1)/2\).
3. \(6\) điểm: \(k=0\).
4. \(19\) điểm: \(k\le n\).
5. \(22\) điểm: \(k\le n(n-1)/8\).
6. \(38\) điểm: không có ràng buộc thêm.

3 2

1 1
1 2
2 2

Khoảng cách từ \((1,1)\) tới \((1,2)\) và từ \((1,2)\) tới \((2,2)\) đều bằng \(1\). Khoảng cách từ \((1,1)\) tới \((2,2)\) bằng \(\sqrt2\), không phải số nguyên.

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.