Digitalisation

Tomorrow Programming School의 학생들은 지역 대부분의 학교가 참여하는 전국 입학 절차(SAP)를 통해 입학한다. SAP는 두 라운드로 구성된다.

첫 번째 라운드가 시작되면 각 학생은 두 학교에 지원하고 우선순위를 적는다. 첫 번째 우선순위와 두 번째 우선순위 학교가 하나씩 있다. 전국 시험은 학생마다 서로 다른 점수를 매기고, 점수가 높은 순서로 정렬된 공동 목록 CL을 만든다. 최고점이 목록의 맨 앞에 온다. 모든 학교는 CL을 볼 수 있다. 각 학교는 점수가 더 좋은 학생을 뽑고 싶어 한다. 각 학교의 정원은 $C$로 제한되며, 각 학교가 가진 후보자 목록도 최대 $C$명까지 담는다. 모든 후보자 목록은 처음에 비어 있다.

두 번째 라운드는 한 번 이상의 사이클로 이루어진 갱신 이벤트로 구성된다. 한 사이클에서는 각 학교가 차례대로 갱신 이벤트를 한 번씩 수행한다.

갱신 이벤트에서 학교 $L$은 CL의 끝, 즉 점수가 가장 낮은 지원자부터 거꾸로 탐색한다. 그리고 다음 조건을 모두 만족하는 첫 지원자 $A$를 고른다.

• $L$이 가득 차 있지 않거나, $A$의 점수가 $L$의 후보자 중 최저 점수보다 좋다.
• 학교 $L$이 $A$의 첫 번째 또는 두 번째 우선순위 학교이다.
• $A$가 어느 후보자 목록에도 없거나, $A$의 두 번째 우선순위 학교의 후보자 목록에 있다.

학교 $L$이 조건을 만족하는 지원자를 고르지 못하면 이 갱신 이벤트는 빈 이벤트이며 종료된다. 고를 수 있으면, $L$이 가득 차 있을 때 $L$에서 점수가 가장 낮은 후보자를 제거한다. 그다음 $A$를 $L$에 넣는다. $A$가 다른 학교의 후보자 목록에 이미 있었다면 그 목록에서 $A$를 뺀다. 이 갱신 이벤트는 유효하다.

한 사이클에서 유효한 갱신 이벤트가 하나라도 있으면 새 사이클을 다시 시작한다. 한 사이클의 갱신 이벤트가 모두 빈 이벤트이면 두 번째 라운드가 끝난다. 그 후 각 학교는 자기 후보자 목록에 있는 학생을 입학시킨다.

통계 담당자는 첫 번째 우선순위 학교에 입학한 학생 수와 두 번째 우선순위 학교에 입학한 학생 수를 알고 싶어 한다.

첫 줄에 세 정수 $N$, $M$, $C$가 주어진다($2 \le N, M \le 10^5$; $1 \le C \le 100$). 각각 지원자 수, 학교 수, 공동 정원 상한이다.

이어지는 $N$개 줄 각각에는 한 학생의 첫 번째 우선순위와 두 번째 우선순위가 $1$부터 $M$까지의 학교 번호로 주어진다. 각 줄은 학생 점수의 내림차순으로 정렬되어 있다.

한 줄에 두 수를 출력한다. 첫 번째 우선순위 학교에 입학한 학생 수와 두 번째 우선순위 학교에 입학한 학생 수이다.