C. Binary String Reconstruction

C. Binary String Reconstruction

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Consider the following process. You have a binary string (a string where each character is either 0 or 1) ww of length nn and an integer xx. You build a new binary string ss consisting of nn characters. The ii-th character of ss is chosen as follows:

• if the character wi−xwi−x exists and is equal to 1, then sisi is 1 (formally, if i>xi>x and wi−x=wi−x= 1, then si=si= 1);
• if the character wi+xwi+x exists and is equal to 1, then sisi is 1 (formally, if i+x≤ni+x≤n and wi+x=wi+x= 1, then si=si= 1);
• if both of the aforementioned conditions are false, then sisi is 0.

You are given the integer xx and the resulting string ss. Reconstruct the original string ww.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

Each test case consists of two lines. The first line contains the resulting string ss (2≤|s|≤1052≤|s|≤105, each character of ss is either 0 or 1). The second line contains one integer xx (1≤x≤|s|−11≤x≤|s|−1).

The total length of all strings ss in the input does not exceed 105105.

Output

For each test case, print the answer on a separate line as follows:

• if no string ww can produce the string ss at the end of the process, print −1−1;
• otherwise, print the binary string ww consisting of |s||s| characters. If there are multiple answers, print any of them.

Example

input

Copy

3
101110
2
01
1
110
1

output

Copy

111011
10
-1

=========================================================================

我们先满足必须是0的位置，然后为了尽可能满足其余1的情况，我们让剩余位置全是1即可，然后在进行无解的判断，条件就按照题目给的写就够了

# include<iostream>
# include<string.h>

using namespace std;

char s[100000+10],t[100000+10];

int main ()
{
    int n;
    cin>>n;

    while(n--)
    {
        scanf("%s",s+1);
        int x;
        cin>>x;

        for(int i=1;i<=strlen(s+1);i++)
        {
            t[i]='1';
        }

        for(int i=1;i<=strlen(s+1);i++)
        {
            if(s[i]=='0')
            {
                if(i-x>=1)
                    t[i-x]='0';
                if(i+x<=strlen(s+1))
                    t[i+x]='0';
            }
        }

        int flag=0;

        for(int i=1;i<=strlen(s+1);i++)
        {
            if(s[i]=='1')
            {
                if(!((i-x>=1&&t[i-x]=='1')||(i+x<=strlen(s+1)&&t[i+x]=='1')))
                {
                    flag=1;
                    break;
                }
            }
            else
            {
                if((i-x>=1&&t[i-x]=='1')||(i+x<=strlen(s+1)&&t[i+x]=='1'))
                    flag=1;

            }
        }

        if(flag)
        {
            cout<<"-1"<<endl;

        }

        else
        {
            for(int i=1;i<=strlen(s+1);i++)
            {
                cout<<t[i];
            }
            cout<<endl;


        }
    }
    return  0;

}