题目描述

你瞄了一眼今天的 "$T3$"：

给定 N 个点的带权无向完全图，求最短的哈密顿回路的长度。

看了下数据范围，你自信满满地写了个状压 dp，然后果断跳去 $T4$，甚至样例都没有测。 “代码不可能会写错的！” 真正的 oier 永远不对拍！你从来没有怀疑过自己的代码能力。

比赛的最后 1 min，你重新读了下题，才发现要求的是最短的哈密顿通路的长度。 “没有时间重写了，从求得的哈密顿回路里贪心丢掉最长的一条边。能骗多少骗多少吧。” -- 这次脑子只转了 1 秒钟，你马上做出了一个最正确的决策。

然后碰上了面对选手代码精心构造数据的出题人，铁了心想要 hack 掉你的贪心做法，他希望能构造这样的数据：

给定 $N$ 和 $L$，要求构造一个 $N$ 个点的带权完全无向图 $G$，满足:

1. 边权范围在 $[1, L]$;
2. 设该图上最短的哈密顿通路的长度为 $h(G)$，而你的错解给出的最优答案（如果存在多种哈密顿回路，运气不错的你总能找到一个去掉最长边后答案最小的结果）是 $f(G)$，需要满足 $f(G) - h(G) >= \lfloor{L/2}\rfloor$。

注： 哈密顿回路是指通过图中所有顶点一次且仅一次的回路； 哈密顿通路是指通过图中所有顶点一次且仅一次的通路。

输入格式

$N\ L$

输出格式

如果无论如何都无法构造满足要求的带权完全图，输出一行 "-1"。

否则输出 $N * N$ 的边权矩阵，满足 $d_{i,j} = d_{j,i}$ 且 $d_{i,i} = 0$。

$0\ d_{1,2}\ ...\ d_{1,n}$ $d_{2,1}\ 0\ ...\ d_{2,n}$ ... $d_{n,1}\ d_{n,2}\ ...\ 0$

样例

样例输入

6 1000

样例输出

0 174 325  60 839 248
174   0 437 398 965 806
325 437   0 658 985 969
 60 398 658   0 319 100
839 965 985 319   0 149
248 806 969 100 149   0

提示

样例 1 解释：

给定图中哈密顿通路的长度是 920，通过的节点分别是 2->1->0->3->5->4； 拥有最长边的最短的哈密顿回路是0->2->1->3->4->5->0，其中最长边是 2->1: 437，去掉最长边后得到的伪哈密顿通路的长度是 1439。

数据范围：

• 约 14 pts：$N = 6$；
• 约 32 pts：$L <= 20$；
• 对于 $100\%$ 的数据：$6 <= N <= 14,\ 10 <= L <= 10^9$。