#1696 영역표시

31  2 s   128 MB  

Description

사막에 몇 마리의 사자가 영역 표시를 해 놓았다. 사막은 NxN 격자 형태로 이루어져 있고, 사막 조사단은 이 중 M개의 격자에서 영역 표시 흔적을 찾았다. 사막 조사단은 영역 표시를 분석해서 그게 어떤 사자의 흔적인지 모두 파악했다. 이 흔적들로 조사단은 어느 사자가 얼마 만큼의 영역을 차지하고 있는지 조사하려고 한다.

사막을 이루고 있는 각각의 격자는 가장 가까이에 영역 표시를 한 사자의 영역으로 간주된다. 여기서 두 격자 간의 거리는 맨해튼 거리(1)로 계산된다. 다만 이렇게 영역을 계산하다보면, 가장 가까이에 여러 사자의 영역 표시가 있는 격자가 존재할 수 있는데, 이런 격자는 분쟁 지역으로 처리한다. 사막 조사단을 도와 각 사자의 영역의 크기와 분쟁 지역의 크기를 계산하시오.

(1) 맨해튼 거리는 두 격자 사이의 X좌표 차이값과 Y좌표 차이값의 합을 의미한다. 예를 들어, 두 격자 (1, 5)과 (2, 4) 사이 거리는 |1-2| + |5-4| = 2 가 된다.

Input

전체 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 사막의 크기를 나타내는 정수 N과 영역 표시의 개수를 나타내는 정수 M이 주어진다.

각 테스트 케이스의 두 번째 줄부터 M개 줄에 걸쳐 영역 표시 정보가 하나씩 주어진다. 영역 표시 정보는 사자의 이름을 나타내는 알파벳 대문자 Ai와 좌표를 나타내는 정수 Xi, Yi로 주어진다.

한 좌표에는 두 개 이상의 영역 표시가 존재하지 않는다.

제약조건

Output

각 테스트 케이스에 대해, 가장 영역을 많이 차지하고 있는 사자부터 가장 영역을 적게 차지하고 있는 사자까지 내림차순으로 사자의 이름과 영역의 크기를 출력한다. 영역의 크기가 같은 경우에는 이름이 알파벳 순으로 우선인 사자부터 출력한다. 그리고 마지막으로 분쟁 지역의 크기를 출력한다.

Sample Input

Sample Output

2
5 3
T 1 1
A 2 4
E 5 1
4 3
Y 1 1
U 1 4
N 4 1
A 10
E 5
T 3
7
N 5
U 5
Y 4
2

HINT

아래의 그림은 첫 번째 테스트 케이스에 대한 답을 나타낸다.

Source

RUN Programming Contest, February 2011