{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"Section1\"\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003cb\u003e\u003cspan style\u003d\"color:black\"\u003eTime Limit:\u003c/span\u003e\u003c/b\u003e\u003cspan style\u003d\"color: black;\"\u003e 7 seconds\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003cb style\u003d\"text-align: center;\"\u003e\u003cspan style\u003d\"color:black\"\u003eMemory Limit: \u003c/span\u003e\u003c/b\u003e\u003cspan style\u003d\"text-align: center; color: black;\"\u003e32 MB\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cdiv\u003e\r\n\t\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\t\t\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003c/div\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;mso-layout-grid-align:none;\r\ntext-autospace:none\"\u003e\r\n\t\t\u003cspan data-scayt_word\u003d\"Baaaam\" data-scaytid\u003d\"1\"\u003eBaaaam\u003c/span\u003e! Another deadly gas bomb explodes in \u003cst1:city\u003e\u003cst1:place\u003eManhattan\u003c/st1:place\u003e\u003c/st1:city\u003e\u0026rsquo;s underworld. Rats have taken over the sewerage and the city council is doing everything to get the rat population under control.\u0026nbsp;\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;mso-layout-grid-align:none;\r\ntext-autospace:none\"\u003e\r\n\t\tAs you know, \u003cst1:city\u003e\u003cst1:place\u003eManhattan\u003c/st1:place\u003e\u003c/st1:city\u003e is organized in a regular fashion with streets and avenues arranged like a rectangular grid. Waste water drains run beneath the streets in the same arrangement and the rats have always set up their nests below street intersections. The only viable method to extinguish them is to use gas bombs like the one which has just exploded. However, gas bombs are not only dangerous for rats. The skyscrapers above the explosion point have to be evacuated in advance and so the point of rat attack must be chosen very carefully.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;mso-layout-grid-align:none;\r\ntext-autospace:none\"\u003e\r\n\t\tThe gas bombs used are built by a company called American Catastrophe Management (ACM) and they are sold under the heading of \u0026ldquo;smart rat gas\u0026rdquo;. They are smart because \u0026mdash; when fired \u0026mdash; the gas spreads in a rectangular fashion through the under street canals. The strength of a gas bomb is given by a number d which specifies the rectangular \u0026ldquo;radius\u0026rdquo; of the gas diffusion area. For example, Figure 2 shows what happens when a bomb with d \u003d 1 explodes.\u003c/p\u003e\r\n\t\u003ccenter\u003e\r\n\t\t\u003cimg src\u003d\"http://uva.onlinejudge.org/external/103/p10360.jpg\" /\u003e\u003c/center\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"mso-layout-grid-align:none;text-autospace:none\"\u003e\r\n\t\t\u003cb\u003e\u003cspan style\u003d\"font-size:18.0pt\"\u003eThe Problem\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;mso-layout-grid-align:none;\r\ntext-autospace:none\"\u003e\r\n\t\tThe area of interest consists of a discrete grid of 1025 \u0026times; 1025 fields. Rat exterminator scouts have given a detailed report on where rat populations of different sizes have built their nests. You are given a gas bomb with strength d and your task is to find an explosion location for this gas bomb which extinguishes the largest number of rats.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;mso-layout-grid-align:none;\r\ntext-autospace:none\"\u003e\r\n\t\tThe best position is determined by the following criteria:\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;mso-layout-grid-align:none;\r\ntext-autospace:none\"\u003e\r\n\t\t\u0026bull; The sum of all rat population sizes within the diffusion area of the gas bomb (given by d) is maximal.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;mso-layout-grid-align:none;\r\ntext-autospace:none\"\u003e\r\n\t\t\u0026bull; If there is more than one of these best positions then the location with the \u0026ldquo;minimal\u0026rdquo; position will be chosen. Positions are ordered first by their x coordinate and second by their y coordinate.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify;mso-layout-grid-align:none;\r\ntext-autospace:none\"\u003e\r\n\t\tFormally, given a location (\u003cspan data-scayt_word\u003d\"x1\" data-scaytid\u003d\"2\"\u003ex1\u003c/span\u003e, \u003cspan data-scayt_word\u003d\"y1\" data-scaytid\u003d\"4\"\u003ey1\u003c/span\u003e) on the grid, a point (\u003cspan data-scayt_word\u003d\"x2\" data-scaytid\u003d\"6\"\u003ex2\u003c/span\u003e, \u003cspan data-scayt_word\u003d\"y2\" data-scaytid\u003d\"8\"\u003ey2\u003c/span\u003e) is within the diffusion area of a gas bomb with strength d if the following equation holds:\u003c/p\u003e\r\n\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"text-align:center;mso-layout-grid-align:\r\nnone;text-autospace:none\"\u003e\r\n\t\t\u003cb style\u003d\"mso-bidi-font-weight:normal\"\u003emax (abs(\u003cspan data-scayt_word\u003d\"x2\" data-scaytid\u003d\"7\"\u003ex2\u003c/span\u003e - \u003cspan data-scayt_word\u003d\"x1\" data-scaytid\u003d\"3\"\u003ex1\u003c/span\u003e), abs (\u003cspan data-scayt_word\u003d\"y2\" data-scaytid\u003d\"9\"\u003ey2\u003c/span\u003e - \u003cspan data-scayt_word\u003d\"y1\" data-scaytid\u003d\"5\"\u003ey1\u003c/span\u003e)) \u0026lt;\u003d d\u003c/b\u003e\u003c/p\u003e\r\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe first line contains the number of scenarios in the input.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tFor each scenario the first line contains the strength\u0026nbsp;d\u0026nbsp;of the gas bomb in the scenario\u0026nbsp;(1 \u0026lt;\u003d\u0026nbsp;d \u0026lt;\u003d\u0026nbsp;50). The second line contains the number\u0026nbsp;n\u0026nbsp;(1 \u0026lt;\u003d\u0026nbsp;n \u0026lt;\u003d\u0026nbsp;20000) of rat populations. Then for every rat population follows a line containing three integers separated by spaces for the position\u0026nbsp;(x,\u0026nbsp;y)\u0026nbsp;and \u0026ldquo;size\u0026rdquo;\u0026nbsp;i\u0026nbsp;of the population\u0026nbsp;(1 \u0026lt;\u003d\u0026nbsp;i \u0026lt;\u003d\u0026nbsp;255). It is guaranteed that position coordinates are valid (i.e., in the range between 0 and 1024) and no position is given more than once.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u003cspan style\u003d\"text-align: justify;\"\u003eFor every problem print a line containing the x and y coordinate of the chosen location for the gas bomb, followed by the sum of the rat population sizes which will be extinguished. The three numbers must be separated by a space.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n1\r\n1\r\n2\r\n4 4 10\r\n6 6 20\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n5 5 30\u003c/pre\u003e"}}]}