#D. A Tide of Riverscape

    远端评测题 1000ms 256MiB

A Tide of Riverscape

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

A Tide of Riverscape

在河边散步时,Mino 默默地记录了一些东西。“时间,”Mino 自言自语道。

“什么?”

“时间和潮汐不等人,”Mino 解释道。“我的名字,取自于这条河,总是提醒我这一点。”

“那你在记录什么?”

“你看,潮汐。每样东西都有自己的周期,我想我已经找到了这个。”

怀疑地,Kanno 偷偷看了看Mino的记录。

记录被表达为一个由字符 '0'、'1' 和 '.' 组成的字符串 $ s $,其中 '0' 表示低潮,'1' 表示高潮,'.' 表示未知的潮汐(可以是高潮或低潮)。

你需要帮助 Mino 确定是否可能在将每个 '.' 独立替换为 '0' 或 '1' 后,给定的整数 $ p $ 不是结果字符串的周期。如果答案是肯定的,请还向 Mino 显示这样的替换。

在这个问题中,如果对于所有 $ 1 \leq i \leq \lvert s \rvert - p $,字符串 $ s $ 的第 $ i $ 个和第 $ (i + p) $ 个字符相同,则正整数 $ p $ 被视为字符串 $ s $ 的周期。其中 $ \lvert s \rvert $ 是 $ s $ 的长度。

输入格式

第一行包含两个用空格分隔的整数 $ n $ 和 $ p $($ 1 \leq p \leq n \leq 2000 $)— 给定字符串的长度和假定的周期。

第二行包含一个长度为 $ n $ 的字符串 $ s $ — Mino 的记录。$ s $ 只包含字符 '0'、'1' 和 '.',且至少包含一个 '.' 字符。

输出格式

输出一行 — 如果可能 $ p $ 不是结果字符串的周期,则输出其中一个这样的字符串;否则输出 "No"(不带引号,你可以以任何大小写形式打印字母)。

样例 #1

样例输入 #1

10 7
1.0.1.0.1.

样例输出 #1

1000100010

样例 #2

样例输入 #2

10 6
1.0.1.1000

样例输出 #2

1001101000

样例 #3

样例输入 #3

10 9
1........1

样例输出 #3

No

提示

In the first example, 7 7 is not a period of the resulting string because the 1 1 -st and 8 8 -th characters of it are different.

In the second example, 6 6 is not a period of the resulting string because the 4 4 -th and 10 10 -th characters of it are different.

In the third example, 9 9 is always a period because the only constraint that the first and last characters are the same is already satisfied.

Note that there are multiple acceptable answers for the first two examples, you can print any of them.

9.10上午8点半作业

未认领
状态
已结束
题目
4
开始时间
2023-9-11 0:00
截止时间
2023-9-18 23:59
可延期
24 小时