保证本题不是 NP 完全问题。
对于一张 的网格图，给出定义：行从 编号，列从 编号。
每个点可用它所在的行编号 与所在的列编号 表示为 。
点 与点 间连有一条无向边，其中 。
定义两个点相邻当且仅当它们之间有连边。
给定 ，有一张 的网格图。
你需要选出这张图的一个生成树，使得所有点的度数乘积最大。
一行两个正整数 。
先输出一个 行 列的 矩阵。第 行第 列为 代表点 与点 间有连边，反之则没有。特别的，第 列必须输出 。
再输出一个 行 列的 矩阵。第 行第 列为 代表点 与点 间有连边，反之则没有。特别的，第 行必须输出 。
输出的每个数间应有空格，两个矩阵之间不应有空行。
任意的最优方案都可以得分。
1 8
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
2 2
1 0 0 0 1 1 0 0
「样例解释 #1」
显然 的网格图只有一种本质不同的生成树。
「样例解释 #2」
「数据范围」
本题采用捆绑测试与 Special Judge。
对于所有测试数据，保证 。
