핸드백

Manhattanila에서 핸드백은 도시 어디서나 인기 있는 기념품이다. 이 도시가 직접 만들기 때문이다.

Manhattanila에는 마을(현지에서는 바랑가이라고 부른다)이 $(a+1)(b+1)$개 있고, $(a+1) \times (b+1)$ 크기의 직사각형 격자로 가지런히 놓여 있다. 각 마을은 정수 두 개 $(x, y)$로 구분한다. $0 \le x \le a$는 행 번호, $0 \le y \le b$는 열 번호이고 둘 다 0부터 센다.

이 가운데 $s$개 마을이 핸드백을 만든다. 이런 마을을 생산 마을이라고 하자. 나머지 마을은 이웃 마을에서 핸드백을 사 온다. 두 마을이 경계를 맞대고 있으면 이웃이므로, 한 마을의 이웃은 동서남북 방향으로 최대 네 곳이다. 이웃이 반드시 생산 마을인 것은 아니다. 이웃도 자기 이웃에서 사 올 수 있고, 공급은 이렇게 계속 이어진다.

생산 마을은 정해진 자기 가격으로 핸드백을 만든다. $p$페소에 파는 이웃에서 사 온 마을은 $p+1$페소에 판다. 모든 마을은 값을 최대한 적게 치른다. 가장 싸게 파는 이웃에서 사 오고, 생산 마을은 자기 생산 가격과 가장 싼 이웃의 가격에 1을 더한 값 중 작은 쪽에 판다. 이 규칙으로 모든 마을의 가격이 하나씩 정해진다.

관광객 한 명이 기념품(pasalubong)을 사러 Manhattanila에 왔다. 친구들에게는 핸드백이 가장 비싼 마을에서 샀다고 자랑할 생각이지만, 실제로는 가장 싼 마을에서 몰래 살 작정이다. 도시에서 핸드백의 가장 비싼 가격은 얼마이고, 그 가격에 파는 마을은 몇 개인지 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에 정수 세 개 $a$, $b$, $s$가 주어진다. $s$는 생산 마을의 수이다. 이어지는 $s$개 줄에는 정수 세 개 $x$, $y$, $p$가 주어진다. 마을 $(x, y)$가 생산 마을이고 핸드백을 $p$페소에 판다는 뜻이다. 한 테스트 케이스 안에서 같은 $(x, y)$는 두 번 주어지지 않는다.

제한

• $1 \le T \le 50000$
• $0 \le a, b \le 10^6$
• $0 \le x \le a$
• $0 \le y \le b$
• $1 \le s \le 30$
• $1 \le p \le 10^9$
• 모든 테스트 케이스의 $s$의 합은 $50000$ 이하이다.

각 테스트 케이스마다 정수 두 개를 공백으로 구분해 한 줄에 출력한다.

• 도시에서 핸드백의 가장 비싼 가격
• 그 가격에 파는 마을의 수