题目内容

实现一个支持过期时间（TTL）的 LRU 缓存，支持以下操作：

• put key value ttl：插入或更新键值对，过期时间为当前时间加 $ttl$ 秒。
• get key：获取 $key$ 的值，若 $key$ 不存在或已过期则返回 $-1$。

缓存容量为 $capacity$。当缓存满时，优先淘汰已过期的条目；若无过期条目，则淘汰最久未使用的未过期条目。

输入描述

第一行包含两个整数 $capacity, q$（$1 \le capacity \le 1000$，$1 \le q \le 10^5$），表示缓存容量和操作数。

接下来 $q$ 行，每行一个操作：put key value ttl timestamp 表示在时间 $timestamp$ 执行插入操作，get key timestamp 表示在时间 $timestamp$ 执行查询操作。其中 $1 \le key, value \le 10^6$，$1 \le ttl \le 10^6$，$timestamp$ 单调递增（$\ge 0$）。

样例 1 里时间 $3$ 出现了两次，因此相等的时间戳是允许的。

输出描述

对每个 get 操作输出一行，返回 $value$ 或 $-1$。

样例 $1$

输入

2 6
put 1 10 100 1
put 2 20 5 2
get 1 3
get 2 3
get 2 8
get 1 50

输出

10
20
-1
10

说明

时间 $1$ 插入 $key = 1, value = 10, ttl = 100$（过期时间 $101$）。时间 $2$ 插入 $key = 2, value = 20, ttl = 5$（过期时间 $7$）。

时间 $3$ 查询 $key = 1$，返回 $10$（未过期）。时间 $3$ 查询 $key = 2$，返回 $20$（未过期）。

时间 $8$ 查询 $key = 2$，过期时间为 $7$，已过期，返回 $-1$。时间 $50$ 查询 $key = 1$，过期时间 $101$ 未过期，返回 $10$。

样例 $2$

输入

2 7
put 1 10 100 1
put 2 20 100 2
put 3 30 100 3
get 1 4
get 2 4
get 3 4
get 3 5

输出

-1
20
30
30

说明

容量为 $2$。时间 $1$ 插入 $key = 1$，时间 $2$ 插入 $key = 2$，缓存已满。

时间 $3$ 插入 $key = 3$，缓存满需淘汰，无过期条目，淘汰最久未使用的 $key = 1$。

查询 $key = 1$ 返回 $-1$（已被淘汰），$key = 2$ 返回 $20$，$key = 3$ 返回 $30$。