Volodya 最近访问了一个非常奇怪的城镇。镇内有N个旅游景点,每两个景点有一条双向路连接。每条道路都有一些分配给它的旅行价格(自然数),并且所有价格都是不同的。但这个小镇最引人注目的是,每个城市观光旅游的总价都是一样的!也就是说,如果我们选择任何城市观光旅游——每个景点都参观一次的循环——旅游道路的成本总和与旅游无关。 Volodya 很好奇是否能找到这样的价格体系,所有公路价格不大于 1000。
输入
输入仅包含一个自然数 (3 ≤ N ≤ 20) — 城镇景点的数量。
输出
输出应包含 N 行,每行包含 N 个正整数 — 价格图的邻接矩阵(因此,第 i 行中的第 j 个数字应等于第 j 个景点和第 i 个景点之间的道路价格)。对角线数应等于零。所有数字不得大于 1000。所有价格均应为正且两两不同。如果有多个解,输出任意一个。
示例
输入 #1
3
输出 #1
0 3 4 3 0 5 4 5 0