版权声明

本题版权归 CTFPC 出题组 所有。

题目描述

2se 给了你一道有趣的数据结构题——

维护两个序列 $\{a_n\},\{b_m\}$（$m \to +\infty$），支持以下操作 $q$ 次：

其中 $\{a_n\}$ 的初值给定，$b_i$ 初始时均为 $-1$。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个正整数 $a_1 \sim a_n$。

下面 $q$ 行，每行一个操作。

输出格式

对每个 ask 操作输出答案。

样例

1 16
5000
ask 1 1
add 2 400
add 4 300
add 6 200
add 8 100
inq 2
ask 1 2
mninq
ask 1 3
mxinq
ask 1 4
update 2 3 10000
ask 1 4
ask 2 4
ask 3 4
ask 4 4

5000
5400
5500
5800
25800
20800
10400
300

数据范围

• $1 \le n \le 2 \times 10^5$。
• $1 \le q \le 2 \times 10^5$。
• $1 \le a_i \le 10^8$。
• $1 \le l \le r \le n+q$。
• $1 \le i \le 2 \times 10^5$。
• $1 \le v \le 10^8$。
• 保证同一个 $b_i$ 只会被赋给非负值最多一次。
• $r$ 不超过当前 $a$ 数组的长度。