C. Кони
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваня расставляет коней на бесконечной шахматной доске. Изначально на доске стоят $$$n$$$ коней. Если пустую клетку бьют хотя бы $$$4$$$ уже поставленных коня, то на неё ставится новый конь. Ваня повторяет эту операцию, пока есть такая пустая клетка. Несложно показать, что процесс конечен. Также несложно показать, что конечная расстановка коней на доске не зависит от порядка, в котором на доску выставляются новые кони.

Ваня попросил вас найти начальную расстановку из $$$n$$$ коней на доске такую, чтобы в конце процесса на доске оказалось не менее $$$\lfloor \frac{n^{2}}{10} \rfloor$$$ коней.

Входные данные

Первая и единственная строка содержит одно число $$$n$$$ ($$$1 \le n \le 10^{3}$$$) — количество коней в изначальной расстановке.

Выходные данные

Выведите $$$n$$$ строк, в каждой строке выведите $$$2$$$ числа $$$x_{i}$$$ и $$$y_{i}$$$ ($$$-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$$$) — координаты $$$i$$$-го коня. Для всех $$$i \ne j$$$ должно быть верно, что $$$(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$$$. То есть все кони должны стоять на различных клетках.

Гарантируется, что решение существует.

Примеры
Входные данные
4
Выходные данные
1 1
3 1
1 5
4 4
Входные данные
7
Выходные данные
2 1
1 2
4 1
5 2
2 6
5 7
6 6
Примечание

Посмотрим на второй пример:

Зелёные нули — это изначальные кони. Клетка $$$(3, \,\, 3)$$$ находится под ударом $$$4$$$ коней на клетках $$$(1, \,\, 2)$$$, $$$(2, \,\, 1)$$$, $$$(4, \,\, 1)$$$ и $$$(5, \,\, 2)$$$, поэтому Ваня поставит нового коня в эту клетку. Клетка $$$(4, \,\, 5)$$$ изначально находится под атакой лишь $$$3$$$ коней на клетках $$$(2, \,\, 6)$$$, $$$(5, \,\, 7)$$$ и $$$(6, \,\, 6)$$$. Однако новый конь в клетке $$$(3, \,\, 3)$$$ тоже атакует клетку $$$(4, \,\, 5)$$$, теперь эта клетка находится под атакой $$$4$$$ коней, и Ваня поставит нового коня в эту клетку. Больше не осталось свободных клеток, которые находятся под атакой $$$4$$$ или более коней, поэтому процесс останавливается. В конце процесса на доске оказалось $$$9$$$ коней, что не меньше $$$\lfloor \frac{7^{2}}{10} \rfloor = 4$$$.