---
title: Vegalengdir
---

Þér er gefið heiltölur $n$ og $k$. Markmiðið þitt er að velja $n$ ólíka heiltölu punkta á $xy$-planinu svo að fyrir nákvæmlega $k$ pör af punktum er Evklíðska fjarlægðin milli punktanna heiltala. Til upprifjunar er Evklíðska vegalengdin milli punkta $(x_1, y_1)$ og $(x_2, y_2)$ $$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.$$

Það má sýna að lausn er ávallt til fyrir takmarkanir verkefnisins.

# Inntak

Eina línan í inntakinu eru tvær heiltölur, $n$ og $k$.

# Úttak

Prentaðu $n$ línur þar sem $i$-ta lína inniheldur tvær heiltölur: $x$ og $y$ hnitin að $i$-ta punktinum. Algildið af hverju hniti má í mestu vera $10^9$.

Ef það eru margar mögulegar lausnir má prenta eitthvað af þeim.

# Takmarkanir

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

# Dæmi

Inntak:
```
3 2
```

Úttak:
```
1 1
1 2
2 2
```

_Útskýring_: Evklíðska vegalengdin milli $(1, 1)$ og $(1, 2)$ er $1$. Vegalengdin milli $(1, 2)$ og $(2, 2)$ er einnig $1$. Hinsvegar er vegalengdin milli $(1, 1)$ og $(2, 2)$, $\sqrt 2$, sem er ekki heiltala.

# Stigagjöf

| Hópur   | Takmarkanir | Stig      |
| :-----: | ----------- | :-------: |
| 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       | Engar frekari takmarkanir | [score=6] |
