背景

杨辉三角能有什么背景呢？

题目描述

给出 n ，输出前 n 行杨辉三角（什么？你不知道杨辉三角，那让陈日天学长告诉你吧，打开浏览器，在网址栏输入www.baidu.com，加载后再搜索框输入杨辉三角，点击百度一下，然后你就会知道的）。

Format

Input

输入包括一行，共一个整数 n 。

Output

输出包括 n 行，表示杨辉三角前 n 行。

Samples

6

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Limitation

对于100%的数据，满足1<=n<=30。