{"problem":{"name":"[EC Final 2022] Aqre","description":{"content":"Given an $n \\times m$ matrix, you need to fill it with $0$ and $1$, such that: - There cannot be **four** consecutive horizontal or vertical cells filled with the same number. - The cells filled with","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9727"},"statements":[{"statement_type":"Markdown","content":"Given an $n \\times m$ matrix, you need to fill it with $0$ and $1$, such that:\n\n- There cannot be **four** consecutive horizontal or vertical cells filled with the same number.\n- The cells filled with $1$ form a connected area. (Two cells are adjacent if they share an edge. A group of cells is said to be connected if for every pair of cells it is possible to find a path connecting the two cells which lies completely within the group, and which only travels from one cell to an adjacent cell in each step.)\n\nPlease construct a matrix satisfying the conditions above and has as many $1$s as possible. Output the maximum number of $1$s, and the matrix.\n\n## Input\n\nThe first line contains an integer $T~(1\\leq T\\leq 10^3)$ -- the number of test cases.\n\nFor each test case, the first line contains two integers $n, m~(2\\leq n, m\\leq 10^3)$.\n\n### It is guaranteed that the sum of $n\\cdot m$ over all test cases does not exceed $10^6$.\n\n## Output\n\nFor each test case, output the maximum number of $1$s in the first line. Then output the matrix in the following $n$ lines. If there are multiple solution, output any.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9727","tags":["2022","Special Judge","O2优化","构造","ICPC","EC Final"],"sample_group":[["3\n2 2\n3 4\n3 8\n","4\n11\n11\n9\n1110\n1110\n1110\n18\n11101110\n10111011\n11011011\n"]],"created_at":"2026-03-03 11:09:25"}}