Digitalisation

The students of Tomorrow Programming School are admitted in the nationwide School Admission Process (SAP), which involves most schools in the region. SAP has two rounds.

At the start of the first round, each student applies to two schools and ranks them: a first priority and a second priority. A national exam gives each student a unique score and produces a common list CL of students sorted by score in descending order, so the highest score comes first. Every school can see CL. Each school prefers students with better scores. Each school has a capacity limit $C$, and each school keeps a candidate list that also holds at most $C$ students. All candidate lists start empty.

The second round consists of one or more cycles of update events. In a cycle, each school, one after another, performs exactly one update event.

In an update event, school $L$ searches CL from its end, starting with the lowest-scoring applicant, and selects the first applicant $A$ who is not in $L$ and meets all of these conditions:

• Either $L$ is not full, or the score of $A$ is better than the worst score among the candidates in $L$.
• School $L$ is either the first or the second priority of $A$.
• $A$ is either on no candidate list, or on the candidate list of $A$'s second priority school.

If school $L$ finds no such applicant, the update event is empty and ends. Otherwise, if $L$ is full, the candidate with the worst score in $L$ is removed from $L$. Then $A$ is added to $L$. If $A$ was already on another school's candidate list, $A$ is removed from that list. The update event is then valid.

If at least one update event in a cycle is valid, another cycle starts. The second round ends when every update event in one cycle is empty. Then each school admits the students on its candidate list.

The statisticians want to know how many students were admitted to their first priority school and how many were admitted to their second priority school.

The first line contains three integers $N$, $M$, and $C$ ($2 \le N, M \le 10^5$; $1 \le C \le 100$), the number of student applicants, the number of schools, and the common capacity limit.

Each of the following $N$ lines contains the first and second priority of one student, given as school labels from $1$ to $M$. The lines are sorted in descending order of the students' scores.

Print two numbers on one line: the number of students admitted to their first priority school, and the number of students admitted to their second priority school.