🏫 题目名称：兔猫信奥学院的“时光字典”

🐰🐱 题目描述

在兔猫信奥学院的魔法图书馆里，加菲老师发现了一本能够记载历史版本的“时光字典”。小兔和小猫可以借助这本字典，在不同的时间戳为同一个关键词记录不同的含义（字符串值），并在任意时刻回溯查询过去的解释。

请你为这本“时光字典”设计数据结构，支持以下两种操作：

1. SET key value timestamp
   在时间戳 timestamp 时，为字符串 key 存储解释 value。
   所有对同一个 key 的 timestamp 保证严格递增。

2. GET key timestamp
   查询时间戳不超过 timestamp 的那次对 key 的存储，返回其对应的 value。
   如果存在多次满足条件的存储，应返回最大 timestamp_prev 对应的 value；
   若从未存储过该 key 或所有 timestamp_prev > timestamp，返回空字符串 ""。

📥 输入格式

第一行：两个整数 Q, K  
Q 表示操作总数，K 表示不同 key 的数量上限  
接下来 Q 行，每行一种操作：
  1 key value timestamp    —— 对 key 执行 SET(key, value, timestamp)
  2 key timestamp          —— 执行 GET(key, timestamp)，需输出查询结果

• (1 \le Q \le 2\times10^5)
• (1 \le K \le 10^5)
• key、value 均由小写字母和数字组成，长度不超过 100。
• (1 \le timestamp \le 10^7)。
• 对同一 key 的所有 SET 操作中，timestamp 保证严格递增。
• GET 操作中的 timestamp 满足 (1 \le timestamp \le) 当前所有 SET 操作中的最大时间戳。

📤 输出格式

对于每一次 GET 操作，输出一行字符串，为所查询到的 value（或空字符串）。

💡 输入输出样例

样例 1

7 3
1 foo bar 1
2 foo 1
2 foo 3
1 foo bar2 4
2 foo 4
2 foo 5
2 baz 10

bar
bar
bar2
bar2

• 第1行 SET("foo","bar",1)
• 第2行 GET("foo",1) → 返回 "bar"
• 第3行 GET("foo",3) → 最近一次 ≤3 的是 timestamp=1，对应 "bar"
• 第4行 SET("foo","bar2",4)
• 第5行 GET("foo",4) → 返回 "bar2"
• 第6行 GET("foo",5) → 返回 "bar2"
• 第7行 GET("baz",10) → "baz" 未被 SET 过，返回空行

样例 2

5 2
2 x 5
1 x v1 5
2 x 4
2 x 5
2 x 6

v1
v1

• 第1行 GET("x",5) → 空
• 第2行 SET("x","v1",5)
• 第3行 GET("x",4) → 4 之前无存储，空
• 第4行 GET("x",5) → "v1"
• 第5行 GET("x",6) → 最近一次 ≤6 的仍然是 timestamp=5，对应 "v1"

📊 数据范围

• 操作总数 (Q \le 2\times10^5)。
• 不同 key 的数量不超过 (K)（输入中可实际使用的 key ≤ K）。
• timestamp 最大为 (10^7)。
• 总 SET+GET 调用次数 ≤ (2\times10^5)。
• 要求整体时间复杂度 (O(Q\log Q)) 左右。