P16360 [BalticOI 2026] Distances

You are given integers $n$ and $k$. Your goal is to pick $n$ distinct integer points on the $xy$-plane such that for exactly $k$ pairs of points, the Euclidean distance between the points is an integer. Recall that the Euclidean distance between points $(x_1, y_1)$ and $(x_2, y_2)$ is $$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.$$ It can be shown that a solution always exists under the constraints of this task.

The only line contains two integers, $n$ and $k$.

Print $n$ lines with the $i$th line containing two integers: the $x$ and $y$ coordinates of the $i$th point. The absolute value of every coordinate must be at most $10^9$. If there are multiple solutions, you can print any of them.

### Explanation The Euclidean distance between $(1, 1)$ and $(1, 2)$ is $1$. The distance between $(1, 2)$ and $(2, 2)$ is also $1$. However, the distance between $(1, 1)$ and $(2, 2)$ is $\sqrt 2$, which is not an integer. ### Constraints - $1 \le n \le 100$ - $0 \le k \le n(n - 1) / 2$ ### Scoring | Subtask | Constraints | Points | | :-----: | ----------- | :-------: | | 1 | $n \le 4$ | $11$ | | 2 | $k = n(n-1)/2$ | $4$ | | 3 | $k = 0$ | $6$ | | 4 | $k \le n$ | $19$ | | 5 | $k \le n(n-1) / 8$ | $22$ | | 6 | No additional constraints | $38$ |