Մուտքում տրված n թվի համար պահանջվում է կառուցել Պասկալի եռանկյուն կազմված n+1 մակարդակներից։ Օրինակ n = 2 դեպքում 

1
1 1
1 2 1

Input

Ոչ բացասական ամբողջ թիվ՝ n ≤ 30:

Output

n+1 հատ տող՝ ամեն տողում Պասկալի եռանկյան համապատասխան մակարդակը։

Example

Input:
3

Output:
1
1 1
1 2 1
1 3 3 1

---

For the number n given in the input, it is required to construct a Pascal triangle consisting of n+1 levels. For example, in the case of n = 2:

1
1 1
1 2 1

Input

Non-negative integer: n ≤ 30.

Output

n+1 rows, each row containing the corresponding level of Pascal's triangle.

Example

Input:
3

Output:
1
1 1
1 2 1
1 3 3 1

---

hide comments

	feodorv: 2019-05-15 20:21:31 Translation?