30997번 - 가중치 복권 스페셜 저지

문제

1ドル$부터 $N$까지의 숫자 중 중복 없이 3ドル$개를 선택해야 하는 특이한 복권이 있다. 이 복권은 $M$명의 사람이 모두 숫자를 고른 후, 다음과 같이 추첨이 진행된다.

• $K$번에 걸쳐 $N$개의 숫자 중 하나를 추첨한다.
• 마지막으로 $N$개의 숫자 중 하나를 보너스로 추첨한다.
• 사람마다 골랐던 3ドル$개의 숫자 중, $K$번의 추첨 동안 나온 숫자가 포함되어 있지 않고, 보너스 추첨 때 나온 숫자가 포함되어 있으면 당첨이 된다.
• 추첨에서 숫자 $i$가 추첨될 확률은 $\displaystyle{\frac{P_i}{\sum_{k=1}^N P_k}}$이며, $P_i$는 $M$명의 사람들이 숫자 $i$를 고른 횟수의 합이다.
• 같은 숫자가 여러 번 추첨될 수 있다.

하루를 포함한 $M$명의 사람들은 이번에 이 특이한 복권의 추첨에 참여하려고 한다. 하루는 지금 나머지 $M-1$명의 사람들이 고른 숫자를 모두 알고 있다. 하루가 복권에 당첨될 확률이 최대가 되도록 3ドル$개의 숫자를 골라주는 프로그램을 작성하라.

입력

첫 번째 줄에 복권에서 선택할 수 있는 숫자의 최댓값 $N,ドル 하루를 포함하여 이번 복권 추첨에 참여하는 인원 $M,ドル 추첨하는 횟수 $K$가 공백으로 구분되어 정수로 주어진다.

두 번째 줄부터 $M - 1$개의 줄에 걸쳐 복권 추첨에 참여하는 $i$번째 사람이 선택한 서로 다른 숫자 3ドル$개 $a_i,ドル $b_i,ドル $c_i$가 공백으로 구분되어 정수로 주어진다.

출력

첫 번째 줄에 하루가 복권에 당첨될 최대 확률을 기약분수 $\displaystyle{\frac{p}{q}}$꼴로 나타내었을 때, 두 정수 $p,ドル $q$를 공백으로 구분하여 출력한다.

두 번째 줄에 하루가 골라야 하는 숫자 3ドル$개를 공백으로 구분하여 출력한다.

당첨될 확률이 최대가 되도록 숫자를 고를 방법이 여러 가지라면, 그중 한 가지 방법을 아무거나 출력한다.

제한

• 5ドル \le N,ドル $M \le 100$
• 1ドル \le K \le 5$
• 1ドル \le a_i,ドル $b_i,ドル $c_i \le N$

힌트