Steps Up

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

Input

A natural number n, where 1 ≤ n ≤ 100

Output

Print the steps in the format shown in the image.

Examples