24549번 - 신촌방위본부의 부대 배치 스페셜 저지

2021년 8월 21일. 2021 ICPC Sinchon Summer Algorithm Camp Contest가 진행되던 중 정체불명의 조직으로부터 공격받았다. 신촌방위본부는 이를 인명피해 없이 막아내고 정체불명의 조직의 은거지를 찾아내는 큰 공을 세웠다. 

ICPC Sinchon 연합은 찾아낸 은거지로 총공격을 준비하던 중에 무수히 많은 코끼리를 투입하기로 결정했다. 이제 코끼리와 신촌 연합 병사들과 함께 적들의 은거지로 총공격을 가하기 이전에 안정적인 부대 진형을 갖추려고 한다. 다만 이미 짠 부대 진형을 엎고 처음부터 다시 부대 진형을 짤 시간이 없다. 따라서 기존에 배치한 병사들의 위치는 그대로 놔두고 빈자리에 코끼리를 배치하려고 한다.

부대의 진형은 $N \times M$ 격자로 구성되어 있으며, 가장 왼쪽 아래 칸이 $(1,1)$, 가장 왼쪽 위 칸이 $(1,M)$, 가장 오른쪽 아래 칸이 $(N,1)$, 가장 오른쪽 위 칸이 $(N,M)$이다. 코끼리는 그림과 같이 앞으로 한 칸, 대각선으로 두 칸 떨어진 지점을 공격한다. 그리고 병사는 위의 한 칸, 좌우 한 칸 공격할 수 있다. 코끼리가 공격할 때 해당 코끼리의 공격 지점에 있는 병사들과 코끼리를 다치게 할 수 있기 때문에 해당 지점에 병사와 코끼리를 배치할 수 없다. 병사들의 공격 지점에 있는 코끼리 또한 다칠 수 있기에 해당 지점에 코끼리를 배치할 수 없다.

코끼리는 신촌 연합의 가장 중요한 전술 무기로 취급받기에 이를 최대한 많이 배치하려고 한다. 최대한 많이 배치할 수 있는 코끼리의 수와 그 위치를 구해보자.

첫 번째 줄에 격자판의 크기를 나타내는 $N$과 $M$, 그리고 이미 배치된 병사들의 수 $K$가 주어진다. ($1 \le N, M \le 300$, $0 \le K \le NM$)

두 번째 줄부터 $K$개의 줄에 걸쳐서 각 병사들의 위치를 나타내는 $x$, $y$가 주어진다. ($1 \le x \le N$, $1 \le y \le M$)

최대한으로 배치가 가능한 코끼리의 수를 출력한다. 그리고 그에 따른 배치 위치도 출력한다.

답이 여러 개인 경우 아무거나 출력하면 된다.