---
title: 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.

# Input

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

# Output

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.

# Constraints

- $1 \le n \le 100$
- $0 \le k \le n(n - 1) / 2$

# Example

Input:
```
3 2
```

Output:
```
1 1
1 2
2 2
```

_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.

# Scoring

| Subtask | Constraints | Points    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 4$   | [score=1] |
| 2       | $k = n(n-1)/2$ | [score=2] |
| 3       | $k = 0$     | [score=3] |
| 4       | $k \le n$   | [score=4] |
| 5       | $k \le n(n-1) / 8$ | [score=5] |
| 6       | No additional constraints | [score=6] |
