Star Printing - 11

Time limit1sMemory limit256 MB

Summary

Recursively build and print a Sierpinski-like star triangle of height N=3·2^k using the fractal rule of stacking scaled copies with exact spacing.

Level: Medium6 of 10
Topics: Recursion, Implementation, Simulation
Solved: No attempts yet

Problem

Print a star triangle of height N. Start with the base triangle of height 3. Whenever the height doubles, place one copy of the previous triangle centered in the upper half, then place two copies of the previous triangle in the lower half with one space between them. Spaces are part of the pattern, so they must be printed with the correct shape on every line.

Input

The first line contains an integer N. N is always of the form 3 × 2^k, where k is an integer and 0 ≤ k ≤ 10.

Output

Print the star pattern from the first line through the N-th line. Each line must keep the correct shape, including the spaces inside and around the stars.

Examples1

Example 1

Input

Expected output

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