{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWhen Bessie comes back from holidays, she finds that the roof and gate of her stall were ripped off by the storm. It makes Bessie feel uncomfortable and she is planning to run away from Farmer John together with other cows. To achieve this, Bessie needs to transmit some data to the other side of the farm. Farmer John becomes aware of it and is going to ruin their plan.\r\n\u003c/p\u003e\u003cp\u003eThere are N+K stalls lining up in a row, where N is always a multiple of K. In each stall, a cow facing north represents a binary bit \"1\", while a cow facing south represents a binary bit \"0\" conversely. And therefore, if we consider the leftmost stall as the most significant digit of the binary code, N+K stalls form a binary code ranging from 0 to 2\u003csup\u003eN+K\u003c/sup\u003e-1, which tells when Bessie will set out. Farmer John would like to bribe some cows with fresh grass in order to flip some bits of the code.\u003c/p\u003e\u003cp\u003eHowever, smart as Bessie is, she arranged the last K bits at the right of the code as the checksum of the previous N bits data. Since Bessie keeps the most intimate links with those K cows, Farmer John cannot bribe the cows in the last K stalls and then modify the last K bits of the code. Farmer John is wondering what is the minimum number of cows he need to bribe in order to change the binary code and ruin the plan but keep the checksum unchanged. Tell Farmer John how to bribe at the same time. If it is impossible to stop Bessie, output ``Go!Go!Go!\u0027\u0027.\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e\u003c/p\u003e\u003cp\u003eHere are how the checksum is generated:\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e1. Split the N bits data into segments with length K, regard them as binary numbers with K digits, then add them up;\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e2. If the result has more than K digits, fill 0s to the left side of the result until its length is a multiple of K, then regard it as the new binary data and repeat step 1;\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e3. Negate (complement) to get the checksum.\u003cbr\u003e\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e\u003c/p\u003e\u003cp\u003eFor example, the data is 001101001000100110101011, and K\u003d8.\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e1. Split the data into segments: 00110100, 10001001, 10101011, then add them up 00110100+10001001+10101011\u003d101101000\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e2. Fill 0s to the sum: 0000000101101000, repeat step 1: 00000001+01101000\u003d01101001\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e3. Negate the sum: 11111111-01101001\u003d10010110\u003cbr\u003e\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003eThus 10010110 is the checksum of the original data.\u003c/p\u003e\u003cp\u003e\u003cbr\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (1 \u0026lt;\u003d T \u0026lt;\u003d 50), indicating the number of test cases.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tFor each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThe first line contains two integers N and K (0 \u0026lt;\u003d N \u0026lt;\u003d 1,000,000, 1 \u0026lt;\u003d K \u0026lt;\u003d 1,000,000, N is a multiple of K). N is the length of data while K is the length of checksum in binary;\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThe second line is a binary code containing N+K digits (0 or 1), indicating the states of N+K stalls. The last K bits are correct checksum of previous N bits data."}},{"title":"Output","value":{"format":"HTML","content":"For each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tIf it is impossible to stop Bessie, output one line \"Go!Go!Go!\";\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tOtherwise, output two lines: the first line contains one integer indicating the minimum number of cows that Farmer John needs to bribe; The second line contains a binary code with N+K digits (0 or 1), indicating the state of stalls from left to right after flipping. If there are several solutions, output any one of them."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2 1\r\n010\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n110\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}