Програмчлалын олимпиадын бодлогын архив

Мэдээлэлзүйн олимпиадад бэлтгэгч сурагчид компьютерийн ард удаан суудаг тул эмч нар тэдний эрүүл мэндэд санаа зовж шинэ видео адаптер бүтээжээ. Тэр нь цэгүүдээ мөр мөрөөр нь биш диагоналиар нь гаргадаг байна. Диагоналиуд төрөл бүрийн урттай тул ингэснээр дэлгэцийг удаан ширтэх аргагүй болдог тул сурагч залхан өөр зүйл хийхээр явах ёстой ажээ. Цэгүүдийг дэлгэцийн зүүн дээд өнцгөөс эхлэн баруун доод өнцөг хүртэл зүүн дороос баруун дээшээ чиглэлтэй бүх диагоналиудын дагуу гаргана. Өгөгдсөн зургийн цэгүүдийг ямар дарааллаар дэлгэцэн дээр гарахыг олох програм зохио. (адаптерын ажиллагааг жишээ оролт, гаралтаас үзнэ үү.)

Input

Дэлгэц нь квадрат хэлбэртэй ба бодлогын оролтын өгөгдлийн эхний мөрөнд нь уг квадратын талын урт хэдэн пиксель байхыг харуулсан N бүхэл тоо байна. Үүний дараа N тооны мөрөнд тус бүрд нь зуугаас хэтрэхгүй N ширхэг тоо зайгаар тусгаарлагдан өгөгдөнө.Энэ нь дэлгэцэнд гарах ёстой цэгүүд юм. 1<=N<=100.

Output

Гаралт дээр шинэ дэлгэцийн хувьд уг цэгүүд ямар дарааллаар гарах ёстойг хэвлэнэ. Цэгүүдийн утгууд буюу тоонуудыг зайгаар тусгаарлан хэвлэнэ.

Example

Input:
4
1  3  6  10
2  5  9  13
4  8  12 15
7  11 14 16

Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16