쥐 소탕 작전

맨해튼은 도로와 대로가 규칙적인 격자 모양으로 뻗어 있고, 그 아래를 지나는 하수도도 같은 격자 구조를 따른다. 쥐들은 도로가 교차하는 지점 바로 아래에 둥지를 트는데, 둥지를 없애는 유일한 방법은 하수도에 가스 폭탄을 터뜨리는 것이다.

폭탄이 터지면 가스가 하수도를 따라 정사각형 모양으로 퍼진다. 폭탄의 세기 $d$는 확산 영역의 정사각형 "반지름"을 뜻한다. 즉, $(x_1, y_1)$에 떨어뜨린 폭탄은 다음 조건을 만족하는 $(x_2, y_2)$의 둥지를 없앤다.

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

도시는 각 축의 좌표가 $0$부터 $1024$까지인 이산 격자다. 가스 폭탄 하나의 세기 $d$와 각 쥐 개체군의 위치·크기가 주어진다. 폭발 위치 역시 정수 좌표 $[0, 1024]$ 범위의 격자점이어야 한다. 없앨 수 있는 쥐의 총합이 가장 큰 위치를 골라라.

동점은 다음과 같이 처리한다.

• 확산 영역 안에 있는 모든 쥐 개체군 크기의 합이 최대여야 한다.
• 그런 위치가 여러 개면, 먼저 $x$ 좌표, 그다음 $y$ 좌표 순으로 가장 작은 위치를 고른다.

첫 줄에는 시나리오의 개수가 주어진다.

각 시나리오는 다음과 같이 구성된다.

• 첫 줄에는 폭탄의 세기 $d$가 주어진다 ($1 \le d \le 50$).
• 둘째 줄에는 쥐 개체군의 수 $n$이 주어진다 ($1 \le n \le 20000$).
• 이어지는 $n$개의 줄에는 각각 공백으로 구분된 세 정수 $x$, $y$, $i$가 주어진다. 이는 개체군의 위치 $(x, y)$와 크기 $i$를 뜻한다 ($1 \le i \le 255$). 모든 좌표는 $0 \le x, y \le 1024$를 만족하며, 같은 위치가 두 번 이상 주어지지 않는다.

각 시나리오마다 한 줄에 공백으로 구분된 세 정수를 출력한다. 고른 폭발 위치의 $x$ 좌표와 $y$ 좌표, 그리고 그곳에서 없앤 쥐 개체군 크기의 총합이다.