Rat Attack

Manhattan is laid out as a regular grid of streets and avenues, and the sewage canals beneath them share the same layout. Rats build their nests under the street intersections, and the only effective way to wipe out a nest is to drop a gas bomb into the canals.

When a bomb explodes, the gas spreads through the canals in a square pattern. A bomb has a strength $d$ that is the square "radius" of its diffusion area: a bomb dropped at $(x_1, y_1)$ destroys a nest at $(x_2, y_2)$ if and only if

$\max(|x_2 - x_1|,\ |y_2 - y_1|) \le d$

The city is a discrete grid whose coordinates run from $0$ to $1024$ on each axis. You are given the strength $d$ of a single gas bomb together with the positions and sizes of the rat populations. The explosion location must itself be a grid field with integer coordinates in $[0, 1024]$. Choose the location that destroys the largest total rat population.

Ties are resolved as follows:

• The sum of the sizes of every rat population inside the diffusion area must be maximal.
• If several locations achieve that maximum, choose the smallest one, ordered first by its $x$ coordinate and then by its $y$ coordinate.

The first line contains the number of scenarios.

Each scenario is described as follows:

• The first line contains the bomb strength $d$ ($1 \le d \le 50$).
• The second line contains the number of rat populations $n$ ($1 \le n \le 20000$).
• Each of the next $n$ lines contains three space-separated integers $x$, $y$ and $i$: the position $(x, y)$ of a population and its size $i$ ($1 \le i \le 255$). Every coordinate satisfies $0 \le x, y \le 1024$, and no position appears more than once.

For each scenario, print a single line with three space-separated integers: the $x$ and $y$ coordinates of the chosen explosion location, followed by the total size of the rat populations destroyed there.