{"problem":{"name":"Ex - Construct a Matrix","description":{"content":"Determine whether there is an $N$\\-by-$N$ matrix $X$ that satisfies the following conditions, and present one such matrix if it exists. (Let $x_{i,j}$ denote the element of $X$ at the $i$\\-th row from","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc276_h"},"statements":[{"statement_type":"Markdown","content":"Determine whether there is an $N$\\-by-$N$ matrix $X$ that satisfies the following conditions, and present one such matrix if it exists. (Let $x_{i,j}$ denote the element of $X$ at the $i$\\-th row from the top and $j$\\-th column from the left.)\n\n*   $x_{i,j} \\in { 0,1,2 }$ for every $i$ and $j$ $(1 \\leq i,j \\leq N)$.\n*   The following holds for each $i=1,2,\\ldots,Q$.\n    *   Let $P = \\prod_{a_i \\leq j \\leq b_i} \\prod_{c_i \\leq k \\leq d_i} x_{j,k}$. Then, $P$ is congruent to $e_i$ modulo $3$.\n\n## Constraints\n\n*   $1 \\leq N,Q \\leq 2000$\n*   $1 \\leq a_i \\leq b_i \\leq N$\n*   $1 \\leq c_i \\leq d_i \\leq N$\n*   $e_i \\in {0,1,2 }$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $Q$\n$a_1$ $b_1$ $c_1$ $d_1$ $e_1$\n$\\vdots$\n$a_Q$ $b_Q$ $c_Q$ $d_Q$ $e_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc276_h","tags":[],"sample_group":[["2 3\n1 1 1 2 0\n1 2 2 2 1\n2 2 1 2 2","Yes\n0 2\n1 2\n\nFor example, for $i=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}$.  \nIn this sample output, we have $x_{1,2}=2$ and $x_{2,2}=2$, so $P=2 \\times 2 = 4$, which is congruent to $e_2=1$ modulo $3$.  \nIt can be similarly verified that the condition is also satisfied for $i=1$ and $i=3$."],["4 4\n1 4 1 4 0\n1 4 1 4 1\n1 4 1 4 2\n1 4 1 4 0","No"]],"created_at":"2026-03-03 11:01:13"}}