Staircase Pattern

Print right-aligned staircase with # characters, n steps.

Your task

Write a complete program: read the input with input() and print the result with print().

Illustration

# n=4
   #
  ##
 ###
####

Example

Input

4

Output

   #
  ##
 ###
####