题目描述

In a land with developed democracy far, far away, presidential elections for the football association are taking place. This land consists of N counties, and each county has its own football association. There are M presidential candidates labeled with 1, 2, … M. Each of the football associations will select exactly one candidate to cast their vote for. The winner of the election is the candidate with the most votes. If multiple candidates get the most amount of votes, the winner is the one with the smallest label.

During the election campaign, candidates visited the counties and tried to gain their sympathies. After having met all the candidates, each county’s football association determined the order in which they would cast their vote for each candidate.

For example, let’s assume that there are four candidates in the election and that one county’s order is 2, 1, 4, 3. This means that, unless they revoke their candidacy, the candidate with label 2 will get the county’s vote. If candidate 2 revokes their candidacy, and candidate 1 is still in the race, then they will get the vote, and so on.

Zdravko is a passionate football fan, and also a close friend of candidate with label K. He wants to know which candidate will win if neither of the candidates revokes their candidacy.

He also wants to know what is the minimal number of candidates he must persuade to revoke their candidacy in order for his friend, candidate K, to become the president of the football association.

Zdravko is currently dealing with other problems, so he is hoping that you will answer these questions.

输入格式

The first line of input contains the numbers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 15) and K (1 ≤ K ≤ M) from the task.

Each of the following N lines contains the orders given by the counties’ football associations, i.e. a permutation of the first M natural numbers.

输出格式

You must output the answers to the questions from the task, each in its own line.

题目翻译

在一个遥远的民主发达的国家里，全国足球协会总负责人选举正在进行。这个国家由N个县组成，每个县都有自己的足球协会，M名负责人候选人被标记为1、2、3、···、M，每个足球协会都会选出一个人进行投票。最终得票最多的候选人便是最终的获胜者，如果有最多票数相同的情况，那么，标号最小的获胜。

在竞选期间，各个候选人访问了各县并试图获得同情，在遇到所有的候选人之后，这个县的足球协会将确定他们为每个候选人投票的顺序。

举个例子，如果我们有四个候选人，一个县选择的顺序为2,1,4,3，不那么，除非他们撤销候选人资格，否则2号候选人将得到这个县的选票，如果2号候选人被撤销候选资格，1号候选人继续参加选举，那么1号候选人将得到这个县的选票，以此类推。

Zdravko是一位充满激情的足球迷，也是K号候选人的密友，他想知道，如果所有的候选人都参加选举，最终哪位候选人能够获胜。

他还希望知道，为了让他的朋友K能够从选举中胜出，他需要最少说服多少名候选人退出选举。

由于Zdravko最近比较繁忙，所以他拜托你帮他解决这个问题。

输入格式

第一行输入三个数字N（1≤N≤100），M（1≤M≤15），K（1≤K≤M）

接下来N行，每行输入M个数字，表示第i个县投票的顺序。

输出格式

第一行输出如果所有候选人都不退出，最终的获胜者是谁。

第二行输出如果要使K胜出，最少需要劝退多少名候选人。

样例 #1

样例输入 #1

3 4 1
3 4 1 2
4 2 3 1
3 4 2 1

样例输出 #1

3
3

样例 #2

样例输入 #2

4 1 1
1
1
1
1

样例输出 #2

1
0

样例 #3

样例输入 #3

4 4 4
2 3 1 4
2 3 1 4
1 3 2 4
4 3 2 1

样例输出 #3

2
3

提示~

Clarification of the first test case:

举行选举的土地由3个县组成，有4名候选人 协会主席。 如果两位候选人都没有撤销其候选人资格，则候选人 3 将获胜 以两票进行的选举。 只有当所有其他候选人都撤销他们的候选人时，候选人 1 才会获胜 候选资格。

Clarification of the second test case:

只有一个候选人，Zdravko 的朋友，所以他们一定会赢。