Problem: Mr. Haskins is working on tuning a database system. The database is a simple associative storage that contains key-value pairs. In this database, a key is a distinct identification (ID) number and a value is an object of any type.

In order to boost the 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 a time is limited. To implement caching, he selected 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 an assistant of Mr. Haskins. He regards you as 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 the following condition: 1 ≤ N, M ≤ 100000.

The following N lines, each containing one ID, represent the sequence of the queries. An ID is a positive integer less than or equal to 109.

Output

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

Example

Input




Output

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <iostream>
#include <set>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define PRIME1 99999883
#define PRIME2 99999893
#define EPS 0.00000001
using namespace std;

struct Node{
	Node(){
		value = -1;
		left_child = -1;
		right_child = -1;
	}

	int value,left_child,right_child;
};

class Tree{

public:
	Tree(int M){
		table = new Node[M];
		size = M;
		index = 0;
	}

	bool add(int num){
		if(index == 0){
			table[index++].value = num;
			return true;
		}else{
			if(index == size)return false;

			int current = 0;

			while(true){
				if(num < table[current].value){
					if(table[current].left_child == -1){
						table[current].left_child = index;
						table[index++].value = num;
						return true;
					}else{
						current = table[current].left_child;
					}
				}else if(num > table[current].value){
					if(table[current].right_child == -1){
						table[current].right_child = index;
						table[index++].value = num;
						return true;
					}else{
						current = table[current].right_child;
					}

				}else{ //num == table[current].value
					return false;
				}
			}
			return false;	//must not reach here
		}
	}
private:
	Node* table;
	int size,index;
};

int main(){

	int N,M,tmp;
	scanf("%d %d",&N,&M);
	Tree tree(M);

	stack<int> S;

	for(int i = 0; i < N; i++){
		scanf("%d",&tmp);
		S.push(tmp);
	}

	printf("%d\n",S.top());
	tree.add(S.top());
	S.pop();

	int count = 1;

	while(count < M && S.empty() == false){
		if(tree.add(S.top())){
			printf("%d\n",S.top());
			count++;
		}
		S.pop();
	}

    return 0;
}