LRU 代表 “Least Recently Used”（最近最少使用）。在计算机系统中，这一技巧常被用来管理较为紧缺的资源，比如内存或磁盘空间。

想象你有一个小型的缓冲区（buffer）。当你需要获取一个内存对象的时候，首先检查它是否在当中，如果有，那么就可以很快速地返回。但如果buffer里没有，就需要访问更慢的磁盘。这就需要花费更多的时间。

接下来，我们来介绍 LRU 策略。LRU 优先将最近使用过的项目保留在buffer中，并在buffer已满时优先将最近最少使用的项目移除。这一策略的根据是，如果一个对象很久没有被访问，那么之后再去访问它的概率也比较低，因而可以“腾笼换鸟”。

举例说明：

1、现有一个容量为3的buffer

2、最初，buffer为空

3、程序依次访问3个对象：A，B，C。它们都是最近使用的，因而被放在buffer中

4、再次访问C，C刚好在buffer中，称为命中（hit），返回其值

4、现在访问D。D不在buffer中，称为缺失（miss）。因为buffer满了，因此最近最少用的对象（A）被移除，将D放入

5、如果再访问A，那么需要从主存中重新读取，并放到buffer中替换掉最近最少使用的B

如此重复…

本题需要你用链表和数组模拟一个缓存-磁盘二级结构。其中磁盘为一个 int 类型的数组，能够容纳 32 * 1024 * 1024 个 int 型整数，其初始值全为0。每一个链表节点都储存一个“键-值”对，表示在“磁盘”中的一个数组下标对应其中的值。缓存有一个容量上限。需要支持以下操作：

  • 写入：给出数组下标和所赋的值，将值写入模拟的磁盘。需要首先检查cache中是否存在对应项。如果cache是满的，那么最近最少使用的对象应当被移除，以容纳新写入的对象。
  • 读取：按照所给的下标读取值。如果buffer中存在，则返回buffer中的值，并输出hit。如果不存在，则从数组中读取，并输出miss，然后把这个键-值对放入buffer中。
  • 调整大小：调整buffer能够存储的键-值对的个数。如果增大容量，则新的项目均为空；如果减小容量，则在旧的项目中保留最近的。

输入格式：

第一行两个整数，表示buffer的初始大小和操作的数量；

之后的每行可能为下列中的一个：

  • write $position$ $x$：向磁盘中第 $position$ 个整数的位置写入 $x$。其中 $x$ 在 int 范围内，$0 \leqslant position \leqslant 32*1024 * 1024$
  • read $position$：读出磁盘中对应位置的整数值
  • resize $size$：调整 buffer 大小为 $size$

输出格式：

对于每次读取请求，输出一行，包括读取到的值，空一格，输出”hit”或”miss”。