题目描述

在北京大学随机算法课程中，你将会遇到如下问题：

有一个大小为 $n$ 的集合 $S=\{1,2,\ldots,n\}$ 以及一个二元运算 $\circ$。你需要在 $O(n^2)$ 的时间内判定 $\circ$ 是否满足结合律，即判定是否对于所有 $i,j,k\in S$，均有

$$i\circ(j\circ k)=(i\circ j)\circ k.$$

这个问题对于大家来说还是太轻松了。但实际上，这道题的数据并不好造。如果不精心构造，很容易出现大量不满足结合律的三元组，导致随机检查也有极高概率给出正确判定。

因此，现在你的任务是为这道题构造数据。形式化地说，你需要处理 $q$ 组任务。对于第 $x$ 组任务，给定一个目标 $c_x$，你需要构造一个二元运算 $\circ$，使得恰好有 $c_x$ 个三元组满足结合律，即

$$\sum_{i\in S}\sum_{j\in S}\sum_{k\in S} \left[i\circ(j\circ k)=(i\circ j)\circ k\right]=c_x,$$

或者报告无解。

其中 $[P]$ 表示：当命题 $P$ 为真时值为 $1$，否则值为 $0$。

输入格式

第一行包含两个整数 $n,q$，分别表示集合大小和任务组数。

接下来 $q$ 行，每行包含一个整数 $c_x$，表示该组任务的目标。

输出格式

对于每组任务：

• 第一行输出字符串 YES 或 NO，表示是否有解；
• 若输出 YES，接下来输出一个 $n\times n$ 的矩阵描述运算 $\circ$ 的运算表，其中第 $i$ 行第 $j$ 列的整数表示 $i\circ j$ 的值。

样例 1

输入

3 2
27
0

输出

YES
1 1 1
1 1 1
1 1 1
YES
2 2 2
1 1 3
2 2 2

数据范围

对于全部数据：

• $1\le n\le64$；
• $1\le qn^2\le10^6$；
• $0\le c_x\le n^3$。

本题共 $10$ 个子任务，每个子任务 $10$ 分。

子任务

子任务编号	分值	特殊限制
1	10	$n\le3$
2		$n\le8$
3		保证所有 $c_x\le n$
4		保证所有 $c_x\ge n^3-n$
5		保证所有 $c_x=0$
6		保证所有 $c_x\equiv0\pmod n$
7		保证所有 $c_x\equiv0\pmod{n^2}$
8		保证输入文件为下发文件中的 random8.in
9		$1\le qn^3\le10^6$
10		无特殊限制