{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003e\"Oh, no!\" --- Petya said, walking around his recently bought ground plot. Petya wants to build a new house on it. According to Petya\u0027s building project the house should look from above like \"C\" character. \u003cbr\u003eThere are many trees growing on Petya\u0027s plot. But everyone who cuts down a tree in Petya\u0027s country is sent to cut down trees for the rest of his life. So first of all Petya has to choose a place for building the house without cutting any tree. \u003cbr\u003eHe is feeling that he is not able to find the solution on his own, so he decided to ask you to help him. \u003cbr\u003eThe task is simplified a little by the fact that Petya\u0027s plot has a rectangular shape of size N*M, divided into 1*1 square cells. For each cell it is known whether there are any trees growing there. House can\u0027t occupy cells where trees grow. \u003cbr\u003eFortunately Petya could explain how his house must look from above. \u003cbr\u003e1) House must consist of three rectangular blocks. \u003cbr\u003e2) Area of each block must be greater than zero. \u003cbr\u003e3) These blocks must touch each other, but can\u0027t overlap. \u003cbr\u003e4) Left-top cells of all blocks must be on one vertical. \u003cbr\u003e5) The width of the middle block must be less than the width of upper and lower blocks. \u003cbr\u003ePetya wants to build a house with maximal possible area. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eThe first line of input contains integers N and M (1\u0026lt;\u003dN,M\u0026lt;\u003d180) separated by whitespace. Each of the following N lines contains M integer numbers separated by whitespaces. Each number is either 0 or 1; 1 means that there are trees in the cell, 0 means that the cell is empty. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eOn the first line output maximal possible area. After that output N lines that describe your plan in the same format as in the input. If the cell is occupied by the house, write 8 instead of 0. If it is impossible to solve problem, output \"-1\" (without quotes). \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eSample test(s)\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eInput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eTest #1 \u003cbr\u003e8 7 \u003cbr\u003e1 1 1 1 1 1 1 \u003cbr\u003e1 1 0 0 0 0 1 \u003cbr\u003e1 1 0 0 0 0 1 \u003cbr\u003e1 1 0 0 0 0 1 \u003cbr\u003e1 1 0 0 0 0 1 \u003cbr\u003e1 1 0 0 0 0 1 \u003cbr\u003e1 1 1 1 1 1 1 \u003cbr\u003e1 1 1 1 1 1 1 \u003cbr\u003e \u003cbr\u003eTest #2 \u003cbr\u003e8 8 \u003cbr\u003e1 1 1 1 1 1 1 1 \u003cbr\u003e1 0 0 0 0 1 0 1 \u003cbr\u003e1 1 1 1 0 0 0 1 \u003cbr\u003e1 0 0 0 0 0 0 1 \u003cbr\u003e1 1 0 0 0 0 0 1 \u003cbr\u003e1 0 1 0 1 0 0 1 \u003cbr\u003e1 0 0 0 0 0 1 1 \u003cbr\u003e1 1 1 1 1 1 1 1 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eOutput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eTest #1 \u003cbr\u003e19 \u003cbr\u003e1 1 1 1 1 1 1 \u003cbr\u003e1 1 8 8 8 8 1 \u003cbr\u003e1 1 8 8 8 8 1 \u003cbr\u003e1 1 8 8 8 0 1 \u003cbr\u003e1 1 8 8 8 8 1 \u003cbr\u003e1 1 8 8 8 8 1 \u003cbr\u003e1 1 1 1 1 1 1 \u003cbr\u003e1 1 1 1 1 1 1 \u003cbr\u003eTest #2 \u003cbr\u003e12 \u003cbr\u003e1 1 1 1 1 1 1 1 \u003cbr\u003e1 0 0 0 0 1 0 1 \u003cbr\u003e1 1 1 1 0 0 0 1 \u003cbr\u003e1 0 0 8 8 8 8 1 \u003cbr\u003e1 1 0 8 8 8 8 1 \u003cbr\u003e1 0 1 8 1 0 0 1 \u003cbr\u003e1 0 0 8 8 8 1 1 \u003cbr\u003e1 1 1 1 1 1 1 1 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003chr\u003e\u003c/div\u003e\u003ctable align\u003d\"left\" cellspacing\u003d\"7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003eAuthor:\u003c/td\u003e\u003ctd\u003eAntony Popovich \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eResource:\u003c/td\u003e\u003ctd\u003ePetrozavodsk Summer Training Sessions 2004 \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eDate:\u003c/td\u003e\u003ctd\u003eAugust 25, 2004 \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e \u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\r\n\u003c/div\u003e"}}]}