Zigzag Pattern

Print zigzag of * for n rows.

Your task

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

Example

Input

3

Output

*   *
 * *
  *