28823번 - Добрых снов 스페셜 저지다국어

문제

Путешествуя по миру, в одной из глубоких горных шахт Ньют Саламандер обнаружил неизвестный науке ранее вид нюхлей, отличающихся от обычных специфической формой усов. Эти зверьки обладали удивительным свойством: они жили под землей большими семьями и большую часть жизни проводили в спячке, просыпаясь по весне и засыпая снова в конце лета. Найдя их, Ньют пришёл в неописуемый восторг и решил непременно забрать с собой несколько особей для дальнейшего их изучения. К его счастью, на дворе стоял ноябрь, и поэтому все зверьки глубоко спали.

Изучив внутренние помещения своего волшебного сундука, Ньют обнаружил в нём квадратную грядку со стороной $n$. Путем некоторых сложных вычислений он выяснил, что максимальное количество нюхлей, которым будет комфортно одновременно спать в этой грядке, также равно $n$.

Единственной проблемой для Ньюта стал тот факт, что во время транспортировки кто-то из нюхлей может неожиданно проснуться. Специфическая форма усов создавала телепатическую связь между нюхлями из одной семьи, и поэтому если просыпается один нюхль, то просыпается и всё семейство. Чтобы избежать путаницы, волшебник решил отвести для каждого семейства минимальную по площади связную часть грядки такую, чтобы каждый нюхль занимал квадрат со стороной 1ドル$. Напомним, что связной частью грядки называется такой набор клеток, что от любой его клетки можно добраться до любой другой, перемещаясь каждый раз в соседнюю по стороне клетку и не выходя за пределы этого набора.

Проснувшись, нюхль сразу начинает копать грядку в одном из четырёх направлений, параллельных сторонам грядки. Направление он выбирает абсолютно случайно. Если вдруг нюхль из одного семейства наткнётся на норку, изначально предназначенную для сна нюхля из другого семейства, то между ними произойдёт конфликт, результатом которого станет разрушение всей грядки.

Помогите Ньюту разместить всех нюхлей на грядке так, чтобы для каждого семейства была отведена минимальная по площади связная часть грядки, и чтобы даже если все зверьки проснутся и начнут копать, нюхли разных семейств ни в коем случае не натыкались на норки друг друга.

입력

Первая строка входных данных содержит единственное число $n$ --- сторона грядки и количество зверьков $(1 \le n \le 10^5)$

Вторая строка содержит $n$ чисел $a_i$ --- семейство, к которому относится $i$-й зверёк $(1 \le a_i \le n)$.

출력

Выведите $n$ строк, содержащих по два целых числа $x_i$ и $y_i$ --- координаты того квадрата грядки, в который следует положить $i$-го зверька.

Гарантируется, что такое размещение нюхлей всегда существует.

제한

힌트