의심스러운 단백질 찾기

클레어는 아미노산이 이어진 서열인 단백질을 연구한다. 단백질은 20종의 아미노산으로 만들어진다. 아미노산에는 알라닌이나 글리신 같은 고유한 이름이 있지만, 보통 한 글자로 표기한다. 그래서 단백질은 DTASDAAAAAALTAABAAAAAKLTABBAAAAAAATAA, TIFLQQQQQQQQQQQ, RICKRQLL처럼 길이가 다른 문자열로 볼 수 있다.

두 단백질을 비교하기는 어렵다. 단백질에는 세포 안에서 기능을 결정하는 활성 부위와 덜 중요한 부분이 함께 있기 때문이다. 학습된 신경망은 단백질을 입력받아 길이 $l$의 수열을 출력한다. 각 수는 단백질의 기능과 관련된 특징에 대략 대응한다. 이 수열을 임베딩이라고 한다.

클레어가 관심을 가지는 것은 다른 단백질과 크게 다른 의심스러운 단백질이다. 그녀는 길이 $l$인 두 임베딩 $p$와 $q$의 차이를 맨해튼 거리로 잰다.

$\mathcal{D}(p, q) = \sum_{i=1}^{l} |p_i - q_i|$

여기서 $p_i$는 임베딩 $p$의 $i$번째 원소이다.

클레어는 $n$개의 단백질 목록에서 $k$개의 의심스러운 단백질을 찾고자 한다. 다음 탐욕 알고리즘을 사용한다.

• 목록의 첫 번째 단백질에서 가장 먼 단백질을 $p^{(1)}$로 고른다.
• $p^{(1)}$에서 가장 먼 단백질을 $p^{(2)}$로 고른다.
• $\min\{\mathcal{D}(p^{(1)}, p^{(3)}), \mathcal{D}(p^{(2)}, p^{(3)})\}$이 최대가 되도록 $p^{(3)}$을 고른다. 이미 고른 두 단백질 모두에서 멀어야 한다.
• $4 \le i \le k$인 각 $i$에 대해, 이미 고른 모든 단백질과의 거리 중 최솟값이 최대가 되도록 $p^{(i)}$를 고른다.

동점이면 목록에서 처음 나오는 단백질을 고른다.

그녀의 구현은 $n$과 $k$가 작을 때는 잘 동작하지만, 값이 커지면 너무 느려진다. 더 빠른 방법을 찾아야 한다.

첫 줄에 세 정수 $n$ ($3 \le n \le 10^4$), $l$ ($1 \le l \le 100$), $k$ ($2 \le k \le \min\{n, 256\}$)가 주어진다. 각각 단백질의 개수, 임베딩의 길이, 고를 단백질의 개수이다.

이어지는 $n$개의 줄은 각각 단백질 식별자로 시작한다. 식별자는 영대문자와 숫자로 이루어진 1자 이상 10자 이하의 문자열이다. 공백 뒤에 임베딩을 정의하는 한 자리 정수 $v_1, \ldots, v_l$ ($0 \le v \le 9$)이 $l$개 주어진다. 모든 식별자는 서로 다르다.

선택한 $k$개 단백질의 식별자를 $p^{(1)}$부터 $p^{(k)}$까지의 순서대로 한 줄에 하나씩 출력한다.