26154번 - 한양 가왕

문제

제9회 한양대학교 프로그래밍 경시대회(HCPC)를 기념하여 한양대학교에서는 "한양 가왕" 행사를 열고자 한다!

행사는 일렬로 나열된 순서대로 1ドル$번부터 $N$번까지 번호가 매겨진 $N$개의 노래방 기계와, 2ドルN$명의 참가자들로 구성되어 진행되는데, 하나의 노래방 기계당 두 명의 참가자들이 배정되어 노래를 부른 후 나오는 점수로 서로 승부를 가리게 된다. 하나의 승부에서 동점자가 없다고 할 때, 다음과 같은 규칙에 따라 하나의 라운드가 진행된다.

• 한 라운드에서 이루어지는 모든 노래방 기계에서의 승부는 동시에 진행된다.
• 1번 노래방 기계에서의 승부에서 패배한 참가자는 $N$번째 기계로 이동하고, 승리자는 자리에 그대로 남는다.
• 그 외에 $i$번째 $(2 \le i \le N)$ 노래방 기계에서의 승부에서 승리한 참가자는 $i-1$번째 기계로 이동하고, 패배자는 자리에 그대로 남는다.

이때 행사를 주관하고 있는 성현이는 모든 참가자들의 "실력 점수"를 알고 있는데, 같은 실력 점수를 가진 참가자가 없고, 모든 승부의 결과는 실력 점수가 더 높은 참가자가 반드시 승리한다는 사실을 성현이는 알고 있다.

$M$개의 라운드 이후 행사가 종료되었을 때의 결과에 따라 결과표를 작성해야 하는 성현이는, 행사 진행을 기다리지 않고 지금 미리 표를 작성해보려고 한다. 성현이를 위해 $M$개의 라운드가 종료된 뒤의 결과를 예측해보자!

입력

첫 번째 줄에 노래방 기계의 수 $N$과 총 라운드의 수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 1\ 000; 0 \le M \le 10^{9})$

이후 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $i$번째 노래방 기계에 배정된 참가자들의 실력 점수 $p_1, p_2$가 공백으로 구분되어 주어진다. $(1 \le p_1, p_2 \le 2N, p_1 \neq p_2)$

출력

$N$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 노래방 기계에 위치해 있는 참가자들의 실력 점수를 오름차순으로 공백을 두고 출력한다.

제한

힌트