18377번 - 은광

은의 땅이라는 별명을 가진 나라가 있다. 이 나라에는 개발되지 않은 많은 은광들이 존재한다 믿어지고 있다. 특이하게도 이 나라에 은광이 존재할 수 있는 점들은 x좌표와 y좌표가 1 이상 N 이하인 N × N개의 격자점이다.

사실 이 나라에는 원래 은광이 하나도 없었다고 한다. 이를 딱하게 여긴 마법사 메시는 마법을 써서 이 나라에 은광을 만들어주기로 했다. 메시가 사용하는 마법은 두 종류이다. 하나는 x좌표가 같은 N개의 점들 중 은광이 있던 점들의 은광을 없애고 없던 점들에 은광을 만드는 것이고, 다른 하나는 y좌표가 같은 N개의 점들에 대해 같은 방법으로 상태를 반전시키는 것이다.

은광 개발업자는 x축 또는 y축과 평행한 변들을 가진 (K - 1) × (K - 1) 정사각형 모양의 땅 R을 사서 R에 포함된 은광들을 모두 개발할 것이다. R의 꼭짓점의 x좌표와 y좌표는 1 이상 N 이하의 정수여야 하며. 이때 은광들을 개발하여 얻게 되는 개발 이익은 R 내부나 경계에 있는 은광의 개수이다. 개발업자는 R에 포함된 은광들의 개발 이익이 최대가 되는 영역 R을 모두 찾을 것이다.

메시의 마법으로 땅의 상태가 바뀔 때마다 (K - 1) × (K - 1) 정사각형 모양의 땅을 사서 얻을 수 되는 최대 개발 이익과, 최대 개발 이익을 얻을 수 있는 방법의 수를 알아내어 은 재벌이 되어보자!

0 × 0 정사각형 모양의 땅을 사면, 격자점 1개의 은광을 개발할 수 있음에 유의하라.

1번째 줄에 나라의 크기 N, 살 수 있는 땅의 크기 K, 메시가 마법을 사용하는 횟수 Q가 공백으로 구분되어 주어진다.

2번째 줄부터 Q개의 줄에 걸쳐 메시가 사용하는 마법에 대한 정보 a, b가 공백으로 구분되어 주어진다. a = 1이면 x좌표가 b인 격자점들의 상태가 반전되고, a = 2이면 y좌표가 b인 격자점들의 상태가 반전된다. (1 ≤ a ≤ 2, 1 ≤ b ≤ N)

메시가 마법을 사용할 때마다 한 줄에 개발할 수 있는 은광의 최대 개수와 그 방법의 수를 공백으로 구분하여 출력한다.

• 1 ≤ K ≤ N ≤ 100,000
• 1 ≤ Q ≤ 100,000