Right-Aligned Star Triangle

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$, print exactly $n$ lines. Line $i$ begins with exactly $n-i$ ordinary spaces, followed by exactly $i$ consecutive *. Every line has exactly $n$ characters counting its leading spaces; no trailing spaces.

Input

One line contains integer $n$.

Output

Print $n$ lines, preserving the specified leading spaces.

Subtasks

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

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

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

Examples

Example 1

Input:

4

Output:

   *
  **
 ***
****

Explanation:

Row i contains n-i leading spaces followed by i stars. For this sample, the input is 4; the displayed rows follow these rules exactly.

Example 2

Input:

1

Output:

*

Explanation:

Row i contains n-i leading spaces followed by i stars. For this sample, the input is 1; the displayed rows follow these rules exactly.