Pascal's Triangle

Problem statement

A mathematics exhibit builds a triangular display one row at a time. Each row begins and ends with a single light, and every interior cell displays the sum of the two cells directly above it. Visitors request a particular number of rows. Your task Generate the first n rows of Pascal's triangle, starting with the row containing only 1. In each later row, boundary entries are 1 and each interior entry is the sum of its two parents. Important details Row one has one value, row two has two, and so on. Print the actual values rather than their sum or a flattened list. For the given bound, every entry fits in a signed 32-bit integer. Worked example For n = 4, the rows are 1; 1 1; 1 2 1; and 1 3 3 1. In the last row, each 3 comes from adding a neighboring 1 and 2 above it.

Input format

One integer n.

Output format

Print n lines, with the values in each row separated by spaces.

Constraints

1 <= n <= 30.

Sample input

4

Sample output

1
1 1
1 2 1
1 3 3 1