Bonus Level

Serhiy was playing Snake and was close to catching the train to LKSH. However, he was unaware that an extra "bonus" level awaited him after the final stage.

This level features an N×N grid, with an apple placed in each cell. Serhiy's snake moves along the diagonals of this grid, consuming the apples as it goes. After completing each diagonal, the snake changes its direction of movement (refer to examples for further clarification).

Input

The input consists of a single integer N (1 ≤ N ≤ 100).

Output

Produce exactly N rows, each containing N numbers. These numbers represent the order in which the snake visits each cell in the grid.

Examples