18485번 - Nine Judges 스페셜 저지다국어

It is time to choose problems for the XCPC finals! There are k problems proposed for the contest, and exactly p of them must be chosen for the final problem set.

The problems have been evaluated by n judges. Each judge has built their own preference list containing all the proposed problems, in order from the problem they like the most to the problem they like the least.

There is still plenty of time until the XCPC finals... well, nobody knows if it is going to be held at all. Therefore, the actual problem set is going to be chosen by an infinite procedure.

Initially, t = 0 and S₀ contains p problems chosen from the proposed k problems uniformly at random. Then, the following sequence of actions will be repeated indefinitely:

• Choose problems i and j such that i ∈ S_t and j ∉ S_t uniformly at random.
• If at least (n+1)/2 judges have put j before i in their preference list, let S_t+1 = S_t \ {i} ∪ {j}. Otherwise, let S_t+1 = S_t.
• Increase t by one.

A problem set S is called plausible if there exists a positive probability threshold ε such that there are infinitely many moments t when the probability of this set being equal to St is more than ε. Here is an equivalent mathematical notation:

S is plausible ⇐⇒ ∃ε > 0 ∀T ≥ 0 ∃t ≥ T: P(S_t = S) > ε

You would like to save the judges some time and find any plausible problem set.

The first line of the input contains three integers n, k, and p (1 ≤ n ≤ 9; n is odd; 1 ≤ p < k ≤ 50 000), denoting the number of judges, the number of problems proposed, and the number of problems to be chosen.

Each of the following n lines contains k integers a_i,1, a_i,2, . . . , a_i,k (1 ≤ a_i,j ≤ k; a_i,j ≠ a_i,j' for j ≠ j'), denoting the preference list of the i-th judge: a_i,1 is the index of the problem they like the most, a_i,2 is the index of the second most liked problem, and so on.

Display p distinct integers between 1 and k in any order, denoting any plausible set of problems.

In the example test case, some other possible answers are 1 2 5 and 2 4 5.