#P18434. Make SYSU Great Again II

Make SYSU Great Again II

Make SYSU Great Again II

  • 标准输入、标准输出;单组数据。

题目描述

你正在参加 CCPC(Chinese Constructive Problem Contest,中国构造题竞赛)。作为“构造王国”的中山大学 SYSU 命题组,自然准备了一道构造题。

原题中的插图:贵校是构造王国吗

给定一个 n×nn\times n 的网格,请在每个格子中填入一个 [0,4n2−1][0,4n^2-1] 范围内的整数,并同时满足:

  1. 每个数在整个网格中最多出现 5 次。
  2. 每个格子恰好填入一个数。
  3. 任意两个有公共边的相邻格子,所填数字的 按位与 必须恰好为 00。

构造任意一个合法方案;如果不存在,报告无解。

输入格式

仅一行,一个整数 nn(1≤n≤20001\le n\le2000),表示网格的边长。

输出格式

如果存在合法方案,第一行输出 Yes,然后输出一个 n×nn\times n 的整数矩阵,表示构造的网格。每个整数必须在 [0,4n2−1][0,4n^2-1] 内。如果存在多种合法方案,输出任意一种。

如果不存在合法方案,仅输出一行 No。

原样例

输入:

4

输出:

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

样例中 0,1,20,1,2 各出现 55 次,44 出现 11 次,所有共边相邻数按位与为 00。无需输出与样例相同的矩阵。