🏫 题目名称：兔猫信奥学院的“时空快照阵列”

🐰🐱 题目描述

在兔猫信奥学院的魔法实验室里，加菲老师准备了一块神奇的“时空阵列”——它能够记录多次状态快照，让小兔和小猫穿梭于不同时间点，读取数组的历史值。

这个阵列有固定长度 n，初始化时每个位置都存放 0。它支持三种操作：

1. SET index val：将当前时刻数组的下标 index 处赋值为 val。
2. SNAP：制作一次快照，返回当前快照编号 snap_id（编号从 0 开始）。
3. GET index snap_id：读取编号为 snap_id 的快照中，数组下标 index 处的数值，并返回它。

加菲老师说：“所有操作一共不会超过 5×10⁴ 次，长度也不会超过 5×10⁴。请你用 O((n+Q)·log Q) 或更优的算法来支持这三种操作！”

📥 输入格式

第一行：两个整数 n, Q  
接下来 Q 行，每行表示一次操作：
  • “1 index val” —— 对应 SET(index, val)  
  • “2”           —— 对应 snap()，需要输出 snap_id  
  • “3 index id”  —— 对应 get(index, id)，需要输出查询结果  

• 1 ≤ n ≤ 50000
• 1 ≤ Q ≤ 50000
• 对于 SET/GET：0 ≤ index < n
• 0 ≤ val ≤ 10^9
• 对于 GET：0 ≤ id < 当前已执行的 SNAP 次数

📤 输出格式

对每一次 SNAP 操作，输出一行快照编号 snap_id；
对每一次 GET 操作，输出一行查询结果数值。
SET 操作不产生输出。

💡 输入输出样例

样例 1

3 5
1 0 5
2
1 0 6
3 0 0
3 0 1

0
5
6

• 操作 1：SET(0,5)
• 操作 2：SNAP → 返回 0
• 操作 3：SET(0,6)
• 操作 4：GET(0,0) → 快照 0 时，array[0]=5
• 操作 5：GET(0,1) → 快照 1 时（第 2 次 SNAP，从 0 开始编号），array[0]=6

样例 2

2 4
2
3 1 0
2
3 1 1

0
0
1
0

• 初始时所有元素为 0
• 第一次 SNAP → 返回 0
• GET(1,0) → 0
• 第二次 SNAP → 返回 1
• GET(1,1) → 0

📊 数据范围

• 数组长度 n、操作次数 Q 均不超过 50000
• 所有操作合计 ≤ 50000
• 要求平均时间复杂度 ≲ O((n+Q)·log Q)