금메달, 은메달, 동메달은 누가 받았을까?
면접 대비시간 제한1초메모리 제한128 MB
두 번의 경기에서 완주할 때마다 기록된 현재 순위를 바탕으로 2차 경기의 최종 순위를 재구성해 상위 3명의 선수 번호를 구하는 문제입니다.
문제
2018년 대한민국 평창에서 동계 올림픽이 열린다. 이번 대회에서는 다음과 같은 새로운 스키 경기 규칙을 적용한다.
스키 경기는 두 번의 경주로 이루어진다. 첫 번째 경주에는 총 N명의 선수가 참가하며, 선수들은 1번부터 N번까지 번호가 붙어 있다. 선수들은 1번부터 N번까지 차례대로 산을 내려온다. 각 선수가 완주할 때마다, 그 시점에서 완주한 선수들 사이의 현재 순위가 정해진다.
첫 번째 경주가 모두 끝나면 최종 순위가 결정된다. 이 순위에서 1등부터 M등까지의 선수만 두 번째 경주에 참가할 수 있다.
두 번째 경주에서는 첫 번째 경주에서 늦게 들어온 순서, 즉 M등부터 1등까지의 순서로 한 명씩 산을 내려온다. 각 선수가 완주할 때마다, 그 시점에서 완주한 선수들 사이의 현재 순위가 정해진다.
두 번째 경주가 모두 끝난 뒤 최종 순위의 1등, 2등, 3등에게 각각 금메달, 은메달, 동메달을 수여한다. 이 세 선수의 번호를 구하라.
모든 선수는 경주를 완주하며, 두 명 이상의 선수가 동시에 들어오는 경우는 없다.
입력
첫 번째 줄에 정수 N과 M이 주어진다. (3 ≤ M ≤ N ≤ 100)
다음 N개의 줄에는 첫 번째 경주에서 각 선수가 완주했을 때 정해진 현재 순위가, 선수 번호 1번부터 N번까지의 순서대로 주어진다.
그다음 M개의 줄에는 두 번째 경주에서 각 선수가 완주했을 때 정해진 현재 순위가, 두 번째 경주에 참가하는 순서대로 주어진다.
출력
첫 번째 줄에 금메달을 받은 선수의 번호를 출력한다. 두 번째 줄에 은메달을 받은 선수의 번호를 출력한다. 세 번째 줄에 동메달을 받은 선수의 번호를 출력한다.