← 返回题目列表

AtCoder · abc276_h

Ex. 构造一个矩阵

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

判断是否存在 N-by-N 矩阵 X 满足以下条件,并呈现一个这样的矩阵(如果存在)。 (让 x_{i,j} 表示元素 X 在 i从顶部数第行和 j左起第 列。)

  • x_{i,j} \in \{ 0,1,2 \} 对于每个 i 和 j (1 \leq i,j \leq N).
  • 以下内容适用于每个 i=1,2,\ldots,Q.
    • 让 P = \prod_{a_i \leq j \leq b_i} \prod_{c_i \leq k \leq d_i} x_{j,k}。然后, P 等于 e_i 模数 3.

约束

  • 1 \leq N,Q \leq 2000
  • 1 \leq a_i \leq b_i \leq N
  • 1 \leq c_i \leq d_i \leq N
  • e_i \in \{0,1,2 \}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N Q
a_1 b_1 c_1 d_1 e_1
\vdots
a_Q b_Q c_Q d_Q e_Q

输出

如果没有矩阵 X 满足条件,打印 No.

如果有一个矩阵 X 满足他们,打印 Yes 在第一行和一个这样的实例 X 在第二行及后续行中采用以下格式。

x_{1,1} x_{1,2} \ldots x_{1,N}
x_{2,1} x_{2,2} \ldots x_{2,N}
\vdots
x_{N,1} x_{N,2} \ldots x_{N,N}

如果多个矩阵满足条件,则接受其中任何一个。


示例输入 1

2 3
1 1 1 2 0
1 2 2 2 1
2 2 1 2 2

示例输出 1

Yes
0 2
1 2

例如,对于 i=2,我们有 P = \prod_{a_2 \leq j \leq b_2} \prod_{c_2 \leq k \leq d_2} x_{j,k}= \prod_{1 \leq j \leq 2} \prod_{2 \leq k \leq 2} x_{j,k}=x_{1,2} \times x_{2,2}.
在此示例输出中,我们有 x_{1,2}=2 和 x_{2,2}=2,所以 P=2 \times 2 = 4,相当于 e_2=1 模数 3.
类似地可以验证,条件也满足 i=1 和 i=3.


示例输入 2

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

示例输出 2

No