별

맑고 달이 없는 밤에는 하늘에서 수백만 개의 별이 반짝이는 것을 볼 수 있다. 이 엄청난 수에 압도된 고대 그리스인들은 약 2,000년 전부터 이 혼돈에 질서를 부여하기 시작했다. 그들은 별들의 무리를 찾아 별자리라고 부르고, 대부분 그리스 신화에서 따온 이름을 붙였는데, 이 이름들은 오늘날까지도 쓰인다. "작은곰자리", "물고기자리", "게자리" 등이 그 예이다.

별자리의 밑그림이 주어져도, 아마추어가 실제 하늘에서 그 별자리를 찾기란 쉽지 않다. 게다가 별 세 개로만 이루어진 "삼각형자리"(Triangulum)처럼 단순한 별자리는 하늘에 여러 번 나타날 수 있어, "진짜" 별자리를 가려내기가 어렵다. 이 문제에서는 컴퓨터로 하늘에서 별자리를 찾는다.

별 지도가 주어진다. 이는 평면 위 점들의 집합이며, 각 점(별)에는 밝기가 하나씩 매겨져 있다. 또한 여러 개의 별자리가 주어지는데, 각 별자리도 평면 위 점들의 집합이다. 각 별자리에 대해 다음을 구해야 한다.

• 그 별자리가 별 지도에 몇 번 나타나는지, 그리고
• 나타나는 경우가 하나라도 있다면, 그중 가장 밝은 것의 밝기.

출현(occurrence)이란, 별자리를 평행이동·회전·양의 배율 크기 조정만으로 옮긴 형태와 일치하는 별 지도의 별 부분집합을 말한다. 즉 방향(향)을 보존하는 닮음 변환만 허용하며, 대칭(거울상, 반사)은 허용하지 않는다. 두 출현은 별 지도의 완전히 같은 별 부분집합으로 이루어졌을 때에만 서로 같은 것으로 본다.

한 출현의 총 밝기는 그 출현을 이루는 별들의 밝기의 합이다. 같은 별자리의 모든 출현은 별의 개수가 같으므로, 총 밝기가 가장 큰 출현이 곧 평균 밝기가 가장 큰 출현이다. 우리는 이 최대 총 밝기를 출력한다.

입력은 여러 개의 별 지도에 대한 설명으로 이루어진다. 각 지도는 별의 개수 $n$을 담은 한 줄로 시작한다($1 \le n < 1000$). 이어지는 $n$개의 줄에는 각각 세 정수, 즉 한 별의 $x$좌표, $y$좌표, 밝기가 주어진다. 값이 클수록 더 밝은 별이다.

그다음 줄에는 뒤따르는 별자리의 개수 $m$이 주어진다($1 \le m < 50$). 각 별자리 설명은 별자리 $i$의 별 개수 $s_i$와 별자리 이름 $N_i$가 담긴 한 줄로 시작한다($N_i$는 최대 40자이며 공백을 포함하지 않는다). 이어지는 $s_i$개의 줄에는 각각 별자리를 이루는 한 점의 $x$좌표와 $y$좌표가 주어진다.

빈 줄이 한 별 지도와 다음 지도를 구분한다. 입력은 빈 지도($n = 0$)로 끝나며, 이 지도는 처리하지 않는다.

모든 별의 좌표는 정수이므로, 회전·크기 조정한 별자리의 점이 정수 좌표에 떨어지지 않는 배치는 곧바로 제외할 수 있다.

각 별 지도에 대해, 먼저 지도 번호("Map #1", "Map #2" 등)를 한 줄에 출력한다.

각 별자리에 대해, 입력과 같은 순서로, 먼저 빈 줄을 하나 출력한 뒤, 별자리 이름과 지도에 나타난 횟수를 다음 형식으로 한 줄에 출력한다.

<이름> occurs <횟수> time(s) in the map.

그 별자리가 한 번 이상 나타난다면, 다음 줄에 모든 출현 중 최대 총 밝기를 다음 형식으로 출력한다.

Brightest occurrence total brightness: <B>

한 번도 나타나지 않으면, 그 별자리에 대한 밝기 줄은 출력하지 않는다.

한 별 지도의 마지막 별자리 뒤에는, 정확히 다섯 개의 붙임표로 이루어진 줄("-----")을 출력한다.