Star Pattern 18

Time limit1sMemory limit256 MB

Summary

Print the size N star figure of nested triangles with alternating orientation defined recursively.

Level: Medium4 of 10
Topics: Recursion, Matrix, Implementation
Solved: No attempts yet

Problem

Print the star figure of size $N$ . The figure of size $n$ takes up $2^n - 1$ lines and $2^{n+1} - 3$ columns, and every cell without a star is a space.

The figure of size 1 is a single star.

When $n \ge 2$ and $n$ is odd, the figure is a triangle pointing up. Put a star in the middle column of the first line, then draw the two slanted sides from that cell. Going down one line at a time, the left side moves one column to the left and the right side moves one column to the right. The last line is all stars, from the leftmost column to the rightmost column. Then draw the figure of size $n - 1$ as well, horizontally centered, on the $2^{n-1} - 1$ lines directly above the last line.

When $n$ is even, the figure is the same shape turned upside down. The first line is all stars, and the two slanted sides move one column inward per line until they meet in the middle column of the last line. The figure of size $n - 1$ is horizontally centered on the $2^{n-1} - 1$ lines directly below the first line.

The two slanted sides and the inner figure occupy different cells, so they never overlap.

Input

The first line contains $N$ ( $1 \le N \le 10$ ).

Output

Print the figure of size $N$ line by line, starting from the first line. Do not print the spaces that follow the last star on a line.

Examples4

Example 1
Input
```
1
```
Expected output
```
*
```
Example 2
Input
```
2
```
Expected output
```
*****
 ***
  *
```

Example 3

Input

Expected output

      *
     * *
    *   *
   *******
  *  ***  *
 *    *    *
*************

Example 4

Input

Expected output

*****************************
 *            *            *
  *          * *          *
   *        *   *        *
    *      *******      *
     *    *  ***  *    *
      *  *    *    *  *
       ***************
        *           *
         *         *
          *       *
           *     *
            *   *
             * *
              *