Cache Control

Interview

Time limit8sMemory limit512 MB

Summary

Simulate an LRU cache of size M over N key accesses, then print the keys still cached from most to least recently used.

Level: Medium5 of 10
Topics: Hash map, Linked list, Simulation, Implementation
Solved: No attempts yet

Problem

Mr. Haskins is tuning a database system. The database is a simple associative storage that holds key-value pairs. A key is a distinct identification (ID) number, and a value is an object of any type.

To improve performance, the database system has a cache mechanism. The cache can be accessed much faster than the normal storage, but the number of items it can hold at one time is limited. To implement caching, he chose the least recently used (LRU) algorithm: when the cache is full and a new item (not in the cache) is being accessed, the cache discards the least recently accessed entry and adds the new item.

You are Mr. Haskins's assistant. He considers you a trusted programmer, so he gave you a task. He wants you to investigate the cache entries after a specific sequence of accesses.

Input

The first line of the input contains two integers N and M. N is the number of accessed IDs, and M is the size of the cache. These values satisfy 1 ≤ N, M ≤ 100000.

The following N lines each contain one ID and represent the sequence of queries. An ID is a positive integer less than or equal to 10^9.

Output

Print the IDs remaining in the cache after executing all queries. Each line must contain exactly one ID. These IDs must appear in the order of their last access time, from the latest to the earliest.

Examples2

Example 1
Input
```
3 2
1
2
3
```
Expected output
```
3
2
```
Example 2
Input
```
5 3
1
2
3
4
1
```
Expected output
```
1
4
3
```