Row-Number Triangle

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given an integer $n$, print $n$ rows. Row $i$ (1-indexed) contains exactly $i$ copies of $i$, separated by one space, without trailing spaces.

Input

One line contains the integer $n$.

Output

Print exactly $n$ rows in the specified format.

Subtasks

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

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

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

Examples

Example 1

Input:

3

Output:

1
2 2
3 3 3

Explanation:

Row i contains i copies of i. For this sample, the input is 3; the displayed rows follow these rules exactly.

Example 2

Input:

1

Output:

1

Explanation:

Row i contains i copies of i. For this sample, the input is 1; the displayed rows follow these rules exactly.