캐시 제어
면접 대비시간 제한8초메모리 제한512 MB
크기 M인 LRU 캐시에 N번의 키 접근을 순서대로 처리한 뒤, 마지막에 남아 있는 키를 최근 사용 순서로 출력한다.
문제
Haskins 씨는 데이터베이스 시스템을 조정하는 작업을 하고 있다. 이 데이터베이스는 키-값 쌍을 저장하는 단순한 연관 저장소다. 여기서 키는 고유한 식별 번호(ID)이고, 값은 임의의 자료형을 가진 객체다.
성능을 높이기 위해 데이터베이스 시스템에는 캐시 메커니즘이 있다. 캐시는 일반 저장소보다 훨씬 빠르게 접근할 수 있지만, 한 번에 담을 수 있는 항목 수가 제한되어 있다. 캐시를 구현하기 위해 그는 LRU(least recently used) 알고리즘을 선택했다. 캐시가 가득 찬 상태에서 캐시에 없는 새 항목에 접근하면, 캐시는 가장 오랫동안 접근되지 않은 항목을 버리고 새 항목을 추가한다.
당신은 Haskins 씨의 조수다. 그는 당신을 믿을 만한 프로그래머로 여겨 특정 접근 순서 이후의 캐시 항목을 조사하는 일을 맡겼다.
입력
입력의 첫째 줄에는 두 정수 N과 M이 주어진다. N은 접근한 ID의 개수이고, M은 캐시의 크기다. 이 값들은 1 ≤ N, M ≤ 100000을 만족한다.
다음 N개의 줄에는 각각 하나의 ID가 주어지며, 이는 질의의 순서를 나타낸다. ID는 10^9 이하의 양의 정수다.
출력
모든 질의를 실행한 뒤 캐시에 남아 있는 ID를 출력한다. 각 줄에는 ID를 정확히 하나씩 출력한다. 이 ID들은 마지막 접근 시각이 늦은 것부터 이른 것 순서로 나타나야 한다.