---
title: Entfernungen
---

Gegeben seien die Ganzzahlen $n$ und $k$. Deine Aufgabe ist es, $n$ verschiedene ganzzahlige Punkte in der $xy$-Ebene auszuwählen, sodass für genau $k$ Paare von Punkten die euklidische Distanz der Punkte ganzzahlig ist. Beachte, dass die euklidische Distanz zwischen den Punkten $(x_1, y_1)$ und $(x_2, y_2)$ definiert ist als $$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.$$

Es ist möglich, zu beweisen, dass unter den gegebenen Einschränkungen immer eine Lösung existiert.

# Eingabe

Die einzige Zeile enthält die Ganzzahlen $n$ und $k$.

# Ausgabe

Gib $n$ Zeilen aus. Die $i$-te davon soll zwei Ganzzahlen enthalten: die $x$- und $y$-Koordinaten des $i$-ten Punktes. Der Betrag jeder Koordinate darf höchstens $10^9$ betragen.

Wenn mehrere Lösungen existieren, darfst du eine beliebige davon ausgeben.

# Beschränkungen

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

# Beispiel

Eingabe:
```
3 2
```

Ausgabe:
```
1 1
1 2
2 2
```

_Erklärung_: Die euklidische Distanz zwischen $(1, 1)$ und $(1, 2)$ ist $1$. Die Distanz zwischen $(1, 2)$ und $(2, 2)$ ist ebenfalls $1$. Die Distanz zwischen $(1, 1)$ und $(2, 2)$ ist allerdings $\sqrt 2$, was keine Ganzzahl ist.

# Bewertung

| Teilaufgabe | Beschränkungen | 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           | Keine weiteren Beschränkungen | [score=6] |
