---
title: Відстані
---

Дано цілі числа $n$ та $k$. Ваша мета — вибрати $n$ різних точок з цілими координатами на $xy$-площині так, щоб рівно для $k$ пар точок евклідова відстань між точками була цілим числом. Нагадаємо, що евклідова відстань між точками $(x_1, y_1)$ та $(x_2, y_2)$ дорівнює $$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.$$

Можна довести, що розв'язок завжди існує під обмеженнями цієї задачі.

# Вхідні дані

Єдиний рядок містить два цілі числа $n$ та $k$.

# Вихідні дані

Виведіть $n$ рядків, де $i$-й рядок містить два цілі числа: координати $x$ та $y$ $i$-ї точки. Модуль кожної координати не повинен перевищувати $10^9$.

Якщо розв'язків декілька, можна вивести будь-який з них.

# Обмеження

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

# Приклад

Вхідні дані:
```
3 2
```

Вихідні дані:
```
1 1
1 2
2 2
```

_Пояснення_: Евклідова відстань між $(1, 1)$ та $(1, 2)$ дорівнює $1$. Відстань між $(1, 2)$ та $(2, 2)$ також дорівнює $1$. Проте відстань між $(1, 1)$ та $(2, 2)$ дорівнює $\sqrt 2$, що не є цілим числом.

# Оцінювання

| Підзадача | Обмеження | Бали    |
| :-----: | ----------- | :-------: |
| 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       | Без додаткових обмежень | [score=6] |
