나는 이 우마를 지배할 수 있다

시간 제한3초메모리 제한1024 MB

요약
합이 0인 비오름차순 정수 우마 점수를 정해 플레이어 K가 정확히 M등이 되도록 하거나, 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 수학, 구현
정답자
아직 제출이 없습니다

문제

마작에서 우마 점수는 게임의 최종 점수에 영향을 미치는 보너스나 페널티를 말하며, 순위에 따라 특정 점수를 더하거나 빼는 방식으로 적용됩니다. 보통 일본식 리치 마작에서 많이 사용되는 규칙 중 하나입니다.

따라서 하나의 마작 게임에서 각 플레이어의 최종 점수는 얼마나 점수를 많이 얻었는지를 나타내는 기본 점수와 순위에 따라서 더하거나 빼지는 우마 점수의 합으로 얻어집니다.

네 명의 플레이어 1,2,3,41, 2, 3, 4가 NN판의 마작 게임을 진행한 결과가 주어집니다. 각 게임마다 플레이어들이 11위부터 44위까지의 서로 다른 순위를 기록하며, 각 순위에 따라 정해진 우마 점수를 반영해 얻은 최종 점수를 자신의 점수에 더합니다. 게임이 시작되기 전에 모든 플레이어의 점수는 00입니다.

NN판의 마작 게임이 모두 끝나고, 44명의 플레이어들은 자신의 점수를 통해 최종 등수를 계산하기로 했습니다. 가장 점수가 높은 사람이 최종 11등, 그 다음으로 높은 사람이 최종 22등이 되고, 마찬가지로 최종 33등과 최종 44등이 결정됩니다.

만약 NN판의 마작 게임이 모두 끝나고 얻은 점수가 같은 두 플레이어가 있다면, 플레이어 번호가 더 작은 플레이어의 최종 등수가 더 높습니다. 예를 들어, 플레이어 22와 플레이어 33이 동점이라면 플레이어 22가 플레이어 33보다 높은 최종 등수를 가집니다.

높은 최종 등수를 가진다는 것은 낮은 수의 최종 등수를 가진다는 뜻입니다. 예시로, 최종 11등과 최종 22등 중 최종 11등, 최종 33등과 최종 44등 중 최종 33등이 높은 최종 등수입니다.

여러분은 순위별로 적절한 우마 점수를 설정하여 NN판의 마작 게임이 모두 끝났을 때, 플레이어 KK를 최종 MM등에 위치하도록 해야 합니다. 이때 우마 점수는 총합이 00이며, 11위부터 44위까지 비오름차순이 되는 정수로 설정해야 합니다.

입력

첫 번째 줄에는 세 정수 N,K,MN, K, M이 공백으로 구분되어 주어집니다. (1≤N≤200,000;1≤K,M≤4)(1 \le N \le 200\\,000; 1 \le K, M \le 4)

두 번째 줄부터 NN개의 줄에 걸쳐 각 마작 게임의 결과가 주어집니다.

  • 각 마작 게임의 결과는 공백으로 구분된 88개의 정수 a_1,a_2,a_3,a_4,s_1,s_2,s_3,s_4a\_{1}, a\_{2}, a\_{3}, a\_{4}, s\_{1}, s\_{2}, s\_{3}, s\_{4}로 주어집니다. 이는 ii위를 기록한 플레이어는 a_ia\_{i}이고, 이때 얻은 기본 점수는 s_is\_{i}임을 의미합니다. (1≤a_1,a_2,a_3,a_4≤4;(1 \le a\_{1}, a\_{2}, a\_{3}, a\_{4} \le 4; i≠j→a_i≠a_j;i \ne j \rightarrow a\_i \ne a\_j; −100≤s_4≤s_3≤s_2≤s_1≤100;-100 \le s\_{4} \le s\_{3} \le s\_{2} \le s\_{1} \le 100; s_1+s_2+s_3+s_4=0)s\_{1} + s\_{2} + s\_{3} + s\_{4} = 0)

출력

각 순위의 우마 점수를 비오름차순으로 −100-100 이상 100100 이하의 정수로 설정해 KK번째 플레이어가 최종 MM등을 할 수 있다면, 이때의 우마 점수 d_1,d_2,d_3,d_4d\_{1}, d\_{2}, d\_{3}, d\_{4}를 공백으로 구분해서 출력합니다. d_id\_i는 ii위의 우마 점수를 의미합니다.

출력은 다음 조건을 만족해야 합니다.

  • −100≤d_4≤d_3≤d_2≤d_1≤100-100 \le d\_{4} \le d\_{3} \le d\_{2} \le d\_{1} \le 100
  • d_1+d_2+d_3+d_4=0d\_{1} + d\_{2} + d\_{3} + d\_{4} = 0
  • d_id\_i는 정수

만약 어떤 우마 점수를 설정하더라도 플레이어 KK를 최종 MM등에 위치하도록 할 수 없다면 단일 정수 -1을 출력합니다.

예제2

  1. 예제 1

    입력
    2 1 2
    1 2 3 4 10 10 -5 -15
    3 2 4 1 20 10 -10 -20
    
    예상 출력
    60 -10 -20 -30
    
  2. 예제 2

    입력
    1 1 4
    1 2 3 4 0 0 0 0
    
    예상 출력
    -1