1234 : 贵校是构造王国吗 II

Description

众所周知，你们正在参加中国构造题竞赛（Chinese Constructive Problem Contest, CCPC），毫无疑问，命题学校中山大学身为构造王国非常希望你们去挑战一些相关的问题。

给定一个 \(n \times n\) 的网格，你需要使用 \([0,4n^2-1]\) 范围内的数字填充，并且满足以下要求。

• 每个数字最多出现 \(5\) 次。

• 每个单元格应填充恰好一个数字。

• 对于任意两个有共同边的相邻单元格，它们按位与的结果应该恰好等于 \(0\)。

构造一个合法的解决方案，或者判断这是不可能的。

Input

输入一个数字 \(n\ (1\le n\le 2000)\)，表示网格的大小。

Output

如果存在合法的解决方案，首先在第一行输出 。然后，输出一个 \(n\times n\) 的整数矩阵，其中每个数字在范围 \([0, 4n^2-1]\) 内，表示你所构造的矩阵。

如果存在多个合法的解决方案，输出其中任意一个即可。

如果不存在合法的解决方案，输出一行 即可。

Sample

4

Yes
0 0 0 0
0 1 2 1
1 2 1 2
2 1 2 4

Hint

Source

Author

SYSU