题目描述

$\qquad$ 塔子哥有一门专业课，叫做操作系统，简称OS。操作系统的页式存储管理中，当主存满并且需要的存储页不在主存中，需要对主存中的页面进行置换，其中有一个非常重要的算法，即LRU置换算法。

$\qquad$ LRU (Least Recently Used)缓存算法理一种常用于管理缓存的策略，其目标是保留最近使用过的数据,而淘汰最久未被使用的数据。实现简单的LRU缓存算法,支持查询、插入、删除操作。

$\qquad$ 最久未被使用定义：查询、插入和删除操作均为一次访问操作，每个元素均有一个最后一次被访问时间,按照最后一次被访问时间排序，时间最早的即为最久未使用。插入操作：当缓存中已经存在，则刷新值，不存在，则插入，如果超过上限，则淘汰最久未被使用的元素。

输入描述

$\qquad$ 第一行两个数N和K，分别表示缓存内最多可以存放页数，以及操作序列中的总操作数。其中N∈[1,100]，K∈[1,10000]。

$\qquad$ 第二至第K+1行，每行两个输入，两个输入用空格分隔。第一个输入是一个字符 $ch_i$ ：A表示插入，Q表示查询，D表示删除。第二个输入是一个整数 $a_i$ ，表示一个页面的编号。其中 $a_i$ ∈[1,100000]。

$\qquad$ 输出一行，表示缓存内各页面的编号，按照LRU优先级。

输入

输出

101 103

解释

缓存大小为2，依次进行插入103、102，重复插入102，查询一次103，插入101时，最久未使用的元素为102，所以淘汰102。

1s, 1024KiB for each test case.