描述 背景 轰！又一枚致命的毒气弹在曼哈顿的地下世界爆炸了。老鼠已经占据了下水道，而市议会正在想尽一切办法控制老鼠的数量。

如你所知，曼哈顿的布局规整，街道和大道呈矩形网格状排列。污水管道在街道下方也以同样的布局延伸，而老鼠总是在街道的交叉点下方筑巢。消灭它们唯一可行的办法就是使用像刚刚爆炸的那种毒气弹。然而，毒气弹不仅对老鼠有危险。爆炸点上方的摩天大楼必须提前疏散人群，所以选择消灭老鼠的地点时必须非常谨慎。

所使用的毒气弹由一家名为美国灾难管理公司（ACM）生产，并且以 “智能灭鼠毒气弹” 的名义出售。它们之所以智能，是因为一旦引爆，毒气会以矩形的形式在街道下的管道中扩散。毒气弹的威力由一个数字 $d$ 来表示， $d$ 指定了毒气扩散区域的矩形 “半径”。例如，图 2 展示了当一枚 $d=1$ 的毒气弹爆炸时的情况。

问题

目标区域是一个由 $1025×1025$ 个方格组成的离散网格。灭鼠侦察员已经给出了关于不同规模的老鼠群体在哪里筑巢的详细报告。你得到了一枚威力为 $d$ 的毒气弹，你的任务是为这枚毒气弹找到一个爆炸位置，以消灭最多数量的老鼠。 最佳位置由以下标准确定： 毒气弹扩散区域（由 $d$ 确定）内所有老鼠群体规模的总和最大。 如果存在多个这样的最佳位置，那么将选择 “最小” 位置的那个。位置首先按其 $x$ 坐标排序，其次按其 $y$ 坐标排序。 正式地说，给定网格上的一个位置 $(x 1 ​ ,y 1 ​ )$ ，如果满足以下等式，那么点 $(x 2 ​ ,y 2 ​ )$ 就在威力为 $d$ 的毒气弹的扩散区域内： $max(∣x 2 ​ −x 1 ​ ∣,∣y 2 ​ −y 1 ​ ∣)≤d$

输入

输入的第一行包含输入中场景的数量。 对于每个场景，第一行包含该场景中毒气弹的威力 $d （ 1≤d≤50 ）$。第二行包含老鼠群体的数量 n （ $1≤n≤20000$ ）。然后对于每一个老鼠群体，接下来有一行包含三个用空格分隔的整数，分别表示位置 $(x,y)$ 和群体规模 $i$ $（ 1≤i≤255 ）$。可以保证位置坐标是有效的（即在 $0$ 到 $1024$ 的范围内），并且没有一个位置会被重复给出。 输出 对于每一个问题，打印一行，包含为毒气弹选择的位置的 $x$ 坐标和 $y$ 坐标，后面跟着将会被消灭的老鼠群体规模的总和。这三个数字必须用一个空格分隔

输入数据 1

1

2

4 4 10

6 6 20

输出数据

5 5 30