{"problem":{"name":"[SDCPC 2023] Difficult Constructive Problem","description":{"content":"Given a string $s_1s_2\\cdots s_n$ of length $n$ where $s_i \\in \\{\\text{0}, \\text{1}, \\text{?}\\}$ and an integer $k$, please fill out all the $\\text{?}$ with $\\text{0}$ or $\\text{1}$ such that the numb","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9566"},"statements":[{"statement_type":"Markdown","content":"Given a string $s_1s_2\\cdots s_n$ of length $n$ where $s_i \\in \\{\\text{0}, \\text{1}, \\text{?}\\}$ and an integer $k$, please fill out all the $\\text{?}$ with $\\text{0}$ or $\\text{1}$ such that the number of indices $i$ satisfying $1 \\le i < n$ and $s_i \\ne s_{i+1}$ equals to $k$. Different $\\text{?}$ can be replaced with different characters.\n\nTo make this problem even more difficult, we ask you to find the answer with the smallest possible lexicographic order if it exists.\n\nRecall that a string $a_1a_2\\cdots a_n$ of length $n$ is lexicographically smaller than another string $b_1b_2\\cdots b_n$ of length $n$ if there exists an integer $k$ ($1 \\le k \\le n$) such that $a_i = b_i$ for all $1 \\le i < k$ and $a_k < b_k$.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $k$ ($1 \\le n \\le 10^5$, $0 \\le k < n$) indicating the length of the string and the required number of indices satisfying the condition.\n\nThe second line contains a string $s_1s_2,\\cdots s_n$ ($s_i \\in \\{\\text{0}, \\text{1}, \\text{?}\\}$).\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor each test case output one line. If the answer exists output the lexicographically smallest one (you need to output the whole given string after filling out all the $\\text{?}$ and make this string the lexicographically smallest); Otherwise output `Impossible`.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9566","tags":["动态规划 DP","贪心","2023","山东","O2优化","分类讨论","省赛/邀请赛"],"sample_group":[["5\n9 6\n1?010??01\n9 5\n1?010??01\n9 6\n100101101\n9 5\n100101101\n9 3\n????????1\n","100100101\nImpossible\n100101101\nImpossible\n000000101\n"]],"created_at":"2026-03-03 11:09:25"}}