题目内容

你需要设计并实现一种缓存结构，遵循最近最少使用（LRU）淘汰规则。该缓存具有固定容量，最多只能同时保存容量个关键字-值对。

缓存必须支持以下两种操作：

• 查询操作 get key：若关键字 key 当前在缓存中，则返回 key 对应的值，并将该关键字调整为最近使用；若不存在，则返回 $-1$。
• 写入操作 put key value：若关键字 key 已经存在，则将其对应的值更新为 value；若不存在，则插入这一组 key-value。插入完成后，如果缓存中的关键字数量超过容量，则需要删除最久未被使用的关键字。

只要某个关键字被 get 或 put 访问，无论是查询还是更新，该关键字都会被视为最近使用。

现在给定缓存容量、操作次数以及若干条操作，请按顺序执行，并输出所有 get 操作的结果。

你实现的 get 和 put 两种操作的平均时间复杂度都需要达到 $O(1)$。

约束条件

• 缓存容量 $capacity$：$1 \le capacity \le 3000$。
• 操作次数 $m$：$1 \le m \le 2 \times 10^5$。
• 关键字 $key$：$0 \le key \le 10000$。
• 值 $value$：$0 \le value \le 10^5$。

输入描述

第一行包含两个整数 $capacity$ 和 $m$，分别表示缓存容量和操作数量。

接下来 $m$ 行，每行描述一条操作，格式如下：

• get key
• put key value

其中 key 表示关键字，value 表示对应的值。

输出描述

对于每一条 get 操作，按顺序输出一行结果。如果 key 存在于缓存中，输出其当前值；否则输出 $-1$。

样例1

输入

2 6
put 1 10
put 2 20
get 1
put 3 30
get 2
get 3

输出

10
-1
30

说明

初始缓存为空，容量为 2。

先执行 put 操作，插入关键字 1 和值 10；再插入关键字 2 和值 20。此时缓存中有关键字 1 和 2，其中 1 较早插入，2 是最近使用。

get 操作查询关键字 1，返回 10，并将 1 调整为最近使用。此时最久未使用变为 2。

随后执行 put 操作插入关键字 3 和值 30。插入后缓存数量为 3，超过容量 2，因此删除最久未使用的 2。

所以后续查询 2 返回 -1，查询 3 返回 30。

样例2

输入

1 6
put 1 1
put 1 2
get 1
put 2 3
get 1
get 2

输出

2
-1
3

说明

容量为 1，缓存最多只能保存一个关键字。

先执行 put 操作插入关键字 1 和值 1。随后再次对关键字 1 执行 put，新值为 2，因为该关键字已经存在，所以只更新值，缓存数量仍为 1。

因此查询 1 返回 2。

接着执行 put 操作插入关键字 2 和值 3。缓存数量变为 2，超过容量 1，于是删除最久未使用的 1。

所以再次查询 1 返回 -1，查询 2 返回 3。

样例3

输入

2 7
put 1 10
put 2 20
get 1
put 2 22
put 3 30
get 1
get 2

输出

10
-1
22

说明

容量为 2。

先执行 put 插入关键字 1 和值 10，再插入关键字 2 和值 20。此时从最久未使用到最近使用的顺序为 1、2。

查询 1 返回 10，并将 1 调整为最近使用。此时顺序变为 2、1，即 2 是最久未使用。

接着对已经存在的关键字 2 执行 put，将值更新为 22，并把 2 调整为最近使用。此时顺序变为 1、2，即 1 是最久未使用。

然后执行 put 插入关键字 3 和值 30。缓存数量超过容量 2，因此删除最久未使用的 1。

最终查询 1 返回 -1，查询 2 返回更新后的值 22。