#abc276h. Ex - Construct a Matrix

Ex - Construct a Matrix

Score : 600600 points

问题描述

确定是否存在一个 NN×NN 矩阵 XX 满足以下条件,并在存在时给出一个这样的矩阵。 (令 xi,jx_{i,j} 表示位于从上到下的第 ii 行和从左到右的第 jj 列处的 XX 的元素。)

  • 对于所有 iijj,有 xi,j{0,1,2}x_{i,j} \in \{0,1,2\},其中 (1i,jN)(1 \leq i,j \leq N)
  • 对于每个 i=1,2,,Qi=1,2,\ldots,Q,满足以下条件:
    • 定义 $P = \prod_{a_i \leq j \leq b_i} \prod_{c_i \leq k \leq d_i} x_{j,k}$,则 PP 除以 33 的余数等于 eie_i

以上为通义千问 qwen-max 翻译,仅供参考。

Problem Statement

Determine whether there is an NN-by-NN matrix XX that satisfies the following conditions, and present one such matrix if it exists. (Let xi,jx_{i,j} denote the element of XX at the ii-th row from the top and jj-th column from the left.)

  • xi,j{0,1,2}x_{i,j} \in \{ 0,1,2 \} for every ii and jj (1i,jN)(1 \leq i,j \leq N).
  • The following holds for each i=1,2,,Qi=1,2,\ldots,Q.
    • Let $P = \prod_{a_i \leq j \leq b_i} \prod_{c_i \leq k \leq d_i} x_{j,k}$. Then, PP is congruent to eie_i modulo 33.

Constraints

  • 1N,Q20001 \leq N,Q \leq 2000
  • 1aibiN1 \leq a_i \leq b_i \leq N
  • 1cidiN1 \leq c_i \leq d_i \leq N
  • ei{0,1,2}e_i \in \{0,1,2 \}
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

NN QQ

a1a_1 b1b_1 c1c_1 d1d_1 e1e_1

\vdots

aQa_Q bQb_Q cQc_Q dQd_Q eQe_Q

Output

If no matrix XX satisfies the conditions, print No.

If there is a matrix XX that satisfies them, print Yes in the first line and one such instance of XX in the following format in the second and subsequent lines.

x1,1x_{1,1} x1,2x_{1,2} \ldots x1,Nx_{1,N}

x2,1x_{2,1} x2,2x_{2,2} \ldots x2,Nx_{2,N}

\vdots

xN,1x_{N,1} xN,2x_{N,2} \ldots xN,Nx_{N,N}

If multiple matrices satisfy the conditions, any of them will be accepted.

Sample Input 1

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

Sample Output 1

Yes
0 2
1 2

For example, for i=2i=2, we have $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}$.
In this sample output, we have x1,2=2x_{1,2}=2 and x2,2=2x_{2,2}=2, so P=2×2=4P=2 \times 2 = 4, which is congruent to e2=1e_2=1 modulo 33.
It can be similarly verified that the condition is also satisfied for i=1i=1 and i=3i=3.

Sample Input 2

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

Sample Output 2

No

update @ 2024/3/10 11:38:46