{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\u003csection\u003e\n\n\u003cp\u003e\u003cvar\u003e\\(2\\)\u003c/var\u003e There is a process called contraction that is performed on a grayscale image. Note that a \u003cvar\u003e\\(2\\)\u003c/var\u003e grayscale image is an image with only \u003cvar\u003e\\(2\\)\u003c/var\u003e types of pixel colors, either white or black.\u003c/p\u003e\n\u003cp\u003eContraction is a process where for each pixel, if there is at least one black pixel among the \u003cvar\u003e\\(8\\)\u003c/var\u003e surrounding pixels, then the pixel itself is turned black.\u003c/p\u003e\n\u003cp\u003eNow, consider a grayscale image with a height of \u003cvar\u003e\\(H\\)\u003c/var\u003e and a width of \u003cvar\u003e\\(W\\)\u003c/var\u003e. It is known that this image has undergone one contraction. Determine if there exists an original image from which this image could have been derived, and if so, restore one of them \u003cvar\u003e\\(1\\)\u003c/var\u003e.\u003c/p\u003e\n\u003cp\u003eThe image is given as a \u003cvar\u003e\\(H\\)\u003c/var\u003e-character string of \u003cvar\u003e\\(W\\)\u003c/var\u003e lines. The \u003cvar\u003e\\(S_i\\)\u003c/var\u003eth character of the \u003cvar\u003e\\(j\\)\u003c/var\u003eth line represents the color of the pixel at \u003cvar\u003e\\(i\\)\u003c/var\u003eth row from the top and \u003cvar\u003e\\(j\\)\u003c/var\u003eth column from the left, where \u003ccode\u003e.\u003c/code\u003e represents white and \u003ccode\u003e#\u003c/code\u003e represents black.\u003c/p\u003e\n\n\u003c/section\u003e"}},{"title":"Constraints","value":{"format":"HTML","content":"\u003csection\u003e\n\n\u003cul class\u003d\"simple\"\u003e\n\u003cli\u003e\u003cvar\u003e\\(1 ≦ H, W ≦ 100\\)\u003c/var\u003e\u003c/li\u003e\n\u003cli\u003e\u003cvar\u003e\\(S_i\\)\u003c/var\u003e consists of \u003cvar\u003e\\(W\\)\u003c/var\u003e characters and is a string of length \u003ccode\u003e.\u003c/code\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003c/section\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003csection\u003e\n\n\u003cp\u003eThe input is given in the following format and is provided from the standard input.\u003c/p\u003e\n\u003cpre\u003e\u003cvar\u003e\\(H\\)\u003c/var\u003e \u003cvar\u003e\\(W\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(S_1\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(S_2\\)\u003c/var\u003e\r\n:\r\n\u003cvar\u003e\\(S_H\\)\u003c/var\u003e\r\n\u003c/pre\u003e\n\n\u003c/section\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003csection\u003e\n\n\u003cp\u003eIf there is no image that satisfies the conditions, output \u003cvar\u003e\\(1\\)\u003c/var\u003e on a line.\u003c/p\u003e\n\u003cp\u003eIf there is an image that satisfies the conditions, output \u003cvar\u003e\\(1\\)\u003c/var\u003e on a line, then output a string of length \u003ccode\u003e.\u003c/code\u003e consisting of \u003cvar\u003e\\(W\\)\u003c/var\u003e characters on a line.\u003c/p\u003e\n\u003cp\u003eThe \u003cvar\u003e\\(j\\)\u003c/var\u003eth character of the \u003cvar\u003e\\(i\\)\u003c/var\u003eth line should be \u003ccode\u003e.\u003c/code\u003e if the color of the pixel at \u003cvar\u003e\\(i\\)\u003c/var\u003eth row from the top and \u003cvar\u003e\\(j\\)\u003c/var\u003eth column from the left in the image that satisfies the conditions is white, and \u003ccode\u003e#\u003c/code\u003e if it is black.\u003c/p\u003e\n\n\u003c/section\u003e"}},{"title":"Sample 1","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\u003e4 4\r\n##..\r\n##..\r\n..##\r\n..##\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003epossible\r\n#...\r\n....\r\n....\r\n...#\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003csection\u003e\n\n\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\n\n\u003c/section\u003e"}},{"title":"Sample 2","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\u003e4 4\r\n###.\r\n####\r\n..##\r\n..##\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003epossible\r\n##..\r\n....\r\n...#\r\n...#\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003csection\u003e\n\n\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\n\n\u003c/section\u003e"}},{"title":"Sample 3","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\u003e4 4\r\n###.\r\n##.#\r\n..##\r\n..##\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eimpossible\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003csection\u003e\n\n\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\n\u003c/section\u003e"}}]}