Codeforces Round #487 (Div. 2) ---B. A Tide of Riverscape

B. A Tide of Riverscape

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

题目链接

Walking along a riverside, Mino silently takes a note of something.
"Time," Mino thinks aloud.
"What?"
"Time and tide wait for no man," explains Mino. "My name, taken from the river, always reminds me of this."
"And what are you recording?"
"You see it, tide. Everything has its own period, and I think I've figured out this one," says Mino with confidence.

Doubtfully, Kanno peeks at Mino's records.

The records are expressed as a string ss of characters '0', '1' and '.', where '0' denotes a low tide, '1' denotes a high tide, and '.' denotes an unknown one (either high or low).

You are to help Mino determine whether it's possible that after replacing each '.' independently with '0' or '1', a given integer pp is not a period of the resulting string. In case the answer is yes, please also show such a replacement to Mino.

In this problem, a positive integer pp is considered a period of string ss, if for all 1≤i≤|s|−p1≤i≤|s|−p, the ii-th and (i+p)(i+p)-th characters of ss are the same. Here |s||s| is the length of ss.

Input

The first line contains two space-separated integers nn and pp (1≤p≤n≤20001≤p≤n≤2000) — the length of the given string and the supposed period, respectively.

The second line contains a string ss of nn characters — Mino's records. ss only contains characters '0', '1' and '.', and contains at least one '.' character.

Output

Output one line — if it's possible that pp is not a period of the resulting string, output any one of such strings; otherwise output "No" (without quotes, you can print letters in any case (upper or lower)).

Examples

input

Copy

10 7
1.0.1.0.1.

output

Copy

1000100010

input

Copy

10 6
1.0.1.1000

output

Copy

1001101000

input

Copy

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

output

Copy

No

Note

In the first example, 77 is not a period of the resulting string because the 11-st and 88-th characters of it are different.

In the second example, 66 is not a period of the resulting string because the 44-th and 1010-th characters of it are different.

In the third example, 99 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.

题意：先输入两个整数n和p，然后输入一个长度为n由‘0’，‘1’，‘.’组成的字符串，‘.’表示未知字符，可以是‘0’或‘1’；

           要求判断该字符串是否是一个周期为p的字符串，只要找到一个不满足的周期为p的情况便输出这种情况，否则都满足周期为p，输出NO

题解：对字符串从头开始便利一遍，每一次判断一下和相隔p的字符是否相等.如果相等继续走，如果不满足再看看两个字符是否有一个为‘.’，如果存在则将‘.’改成与另一个字符不相等的‘0’或‘1’；

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int maxn=1e9+7;
char s[10050];
int main(int argc,char *argv[]){
    /* #ifdef LOCAL
    freopen("C:/Users/Administrator/Desktop/input.txt","r",stdin);
    #endif*/
    int a,b;
    cin>>a>>b;
    scanf("%s",s);
    int flag=1;
    for(int i=0;i<a-b;i++){
            if((s[i]=='0'||s[i]=='1')&&s[i+b]=='.'){
                if(s[i]=='0')s[i+b]='1';
                else s[i+b]='0';
                flag=0;
                break;
            }
            else if((s[i+b]=='0'||s[i+b]=='1')&&s[i]=='.'){
                if(s[i+b]=='1')s[i]='0';
                else s[i]='1';
                flag=0;
                break;
            }
            else if(s[i]=='.'&&s[i+b]=='.'){
                flag=0;
                s[i]='1';
                s[i+b]='0';
                break;
            }
            else if(s[i]!=s[i+b]){
                flag=0;
                break;
            }

    }
    if(flag)cout<<"No"<<endl;
    else {
        for(int i=0;i<a;i++){
            if(s[i]=='.')s[i]='0';
        }
        cout<<s<<endl;
    }
    return 0;
}