peter9244   1년 전

문제

해킨스 씨는 데이터베이스 시스템 조정에 힘쓰고 있습니다. 이 데이터베이스는 키-값 쌍을 포함하는 단순한 연관 저장소입니다.
이 데이터베이스에서 키는 고유한 식별 번호(ID)이고, 값은 어느 타입의 객체입니다.
성능을 높이기 위해서, 이 데이터베이스 시스템은 캐시 메커니즘이 있습니다. 캐시는 일반적인 저장소보다 빠르게 접근하지만, 한 번에 가질 수 있는 아이템의 수는 한정되 있습니다.
캐시를 구현하기 위해서, 그는 LRU 알고리즘 (캐시가 가득차고 캐시에 없는 새로움 아이템이 접근될 때, 캐시는 가장 오랫동안 사용되지 않은 항목을 제거하고 새로운 항목을 추가하는 알고리즘) 을 선택했습니다.
당신은 해킨스 씨의 조수입니다. 그는 당신을 신뢰할만한 프로그래머로 여기고 있어서 그는 당신에게 업무를 줬습니다. 그는 당신이 특정한 접근 순서 이후의 캐시 상태를 연구하기를 바랍니다.


입력

입력의 첫 째줄은 2가지 정수 N, M이 주어집니다. N은 접근된 ID의 수이고, M은 캐시의 사이즈입니다.
이 값들은 다음의 조건을 만족시킵니다. 1<=N,M<=100000
다음의 N개의 줄에는 하나의 ID가 주어지며, 쿼리의 순서를 나타냅니다. ID는 양의 정수이고 10^9이하입니다.

출력

모든 쿼리를 실행한 후 캐시에 남아있는 ID들을 출력하세요. 각각의 줄은 정확하게 하나의 ID를 가져야합니다. 이 ID들은 가장 마지막에 접근된 것부터 가장 오래 전에 접근된 것까지, 접근 시간 기준 내림차순으로 출력되어야 합니다.

댓글을 작성하려면 로그인해야 합니다.