루루의 과수원은 행 열의 격자로 이루어져 있다. 과수원의 위아래와 좌우는 서로 이어져 있다.
위에서부터 각 행에 의 번호를, 왼쪽부터 각 열에 의 번호를 붙인다. 행 번호가 이고 열 번호가 인 칸을 로 나타낸다.
처음에는 서로 다른 개의 칸에 각각 사과나무가 한 그루씩 심어져 있다.
사과나무가 있는 칸을 순서대로 세 번 고르고 고른 칸의 좌표를 각각 라 할 때, 좌표가 인 칸을 세 사과나무의 삼합점이라고 한다.
이때 좌표의 덧셈과 뺄셈은 각 성분에 대해 수행하며, 각 결과는 행 번호를 , 열 번호를 로 나눈 나머지로 바꾼다.
루루는 사과나무가 심어진 세 칸 를 선택하여 삼합점에 사과나무를 심을 수 있다. 선택한 세 칸 중 같은 칸이 여러 번 포함되어도 된다.
삼합점에 이미 사과나무가 심어져 있다면 아무 변화도 일어나지 않는다. 새롭게 사과나무가 심어진 칸도 이후에 선택할 수 있다.
이 과정을 반복했을 때 사과나무가 심어질 수 있는 칸의 개수를 구해 보자.
첫째 줄에 과수원의 행의 수 , 열의 수 , 처음 심어진 사과나무의 수 가 공백을 사이에 두고 주어진다.
이 과정을 원하는 만큼 반복했을 때, 처음 심어진 나무를 포함하여 사과나무가 있을 수 있는 칸의 개수를 출력한다.
이 영상은 문제의 이해와 풀이에 필수적이지 않은 추가 자료이다.
이어서 개의 줄에 걸쳐 처음 사과나무가 심어진 칸의 좌표가 주어진다. 번째 줄에는 번째 사과나무가 심어진 칸의 행 번호 와 열 번호 가 공백을 사이에 두고 주어진다.
처음 사과나무가 심어진 칸은 모두 서로 다르다.
| 4 | 22 |
| 5 | 47 | 추가 제한이 없다. |
