Still such steps

The program takes an integer n as input, representing the number of steps. Your task is to print the steps using spaces and hash symbols #, as illustrated in the example image.

Input

A natural number n, where 1 ≤ n ≤ 100.

Output

Print the steps in the format shown in the image.

Examples