题目描述

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. 最少几个候选人弃权可以使得编号为 $k$ 的候选人当选。

每一问占当前测试点的 $50 \%$ 分数。

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

3
3

4 1 1
1
1
1
1

1
0

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

2
3

提示

The output must consist of two non-empty lines, each containing a single integer. The correct answer to each of the questions is worth 50% of points for that test case.(不会做spj没用)

Clarification of the first test case:

The land where the elections are being held consists of 3 counties, and there are 4 candidates for the president of the association. If neither of the candidates revoke their candidacy, candidate 3 will win the elections with two votes. Candidate 1 will only win if all the other candidates revoke their candidacy.

Clarification of the second test case:

There is only one candidate, Zdravko’s friend, so they will surely win.