---
title: Kaugused
---

Sulle on antud täisarvud $n$ ja $k$. Sinu eesmärk on valida $xy$-tasandil $n$ erinevat täisarvuliste koordinaatidega punkti nii, et täpselt $k$ paari punktide jaoks oleks nende vaheline eukleidiline kaugus täisarv. Meenutame, et punktide $(x_1, y_1)$ ja $(x_2, y_2)$ vaheline eukleidiline kaugus on $$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.$$

Saab näidata, et antud ülesande tingimusi eeldades leidub alati vähemalt üks lahendus.

# Sisend

Sisendi ainsal real on kaks täisarvu $n$ ja $k$.

# Väljund

Väljastada $n$ rida, kui $i$-s rida koosneb kahest täisarvust: $i$-nda punkti $x$- ja $y$-koordinaadid. Iga koordinaadi absoluutväärtus peab olema ülimalt $10^9$.

Kui leidub mitu lahendust, siis väljastada neist ükskõik milline.

# Piirangud

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

# Näide

Sisend:
```
3 2
```

Väljund:
```
1 1
1 2
2 2
```

_Selgitus_: Punktide $(1,1)$ ja $(1,2)$ vaheline eukleidiline kaugus on $1$. Punktide $(1,2)$ ja $(2,2)$ vaheline kaugus on samuti $1$. Punktide $(1,1)$ ja $(2,2)$ vaheline kaugus on aga $\sqrt 2$, mis ei ole täisarv.

# Hindamine

| Alamülesanne | Piirangud | Punkte    |
| :-----: | ----------- | :-------: |
| 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       | Lisapiirangud puuduvad | [score=6] |
