Centered Star Pyramid

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$, print a centered pyramid of exactly $n$ rows. Row $i$ (1-based) starts with $n-i$ spaces followed by $2i-1$ asterisks. Do not add trailing spaces; end each row with a newline.

Input

One line contains integer $n$.

Output

Print exactly $n$ pyramid rows.

Subtasks

• Subtask 1 (20%): $1\le n\le 5$.

• Subtask 2 (30%): $1\le n\le 15$.

• Subtask 3 (50%): $1\le n\le 30$.

Examples

Example 1

Input:

1

Output:

*

Explanation:

Each row has n-i leading spaces and 2i-1 stars.

Example 2

Input:

4

Output:

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

Explanation:

Each row has n-i leading spaces and 2i-1 stars.