题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

接下来有 $q$ 次操作，操作分为如下四种类型：

• $\mathtt{1\ p\ x}$：将 $a_p$ 的数值修改为 $x$；
• $\mathtt{2\ l\ r}$：查询下标区间 $[l, r]$ 范围内所有元素（即 $a_l, a_{l+1}, \ldots, a_r$）的最大值；
• $\mathtt{3\ l\ r}$：查询下标区间 $[l, r]$ 范围内所有元素（即 $a_l, a_{l+1}, \ldots, a_r$）的最小值；
• $\mathtt{4\ l\ r}$：查询下标区间 $[l, r]$ 范围内所有元素（即 $a_l, a_{l+1}, \ldots, a_r$）之和。

对于每次查询操作，你需要输出对应的结果。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \times 10^5)$，表示数列大小。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$，表示初始数列中每个元素的数值。

第三行，一个整数 $q(1 \le q \le 2 \times 10^5)$，表示操作次数。

接下来 $q$ 行，每行包含一次操作，格式为：

• $\mathtt{1\ p\ x}$（$1 \le p \le n, 1 \le x \le 10^9$），或
• $\mathtt{2\ l\ r}$（$1 \le l \le r \le n$），或
• $\mathtt{3\ l\ r}$（$1 \le l \le r \le n$），或
• $\mathtt{4\ l\ r}$（$1 \le l \le r \le n$）。

输出格式

对于每次查询操作，输出一行，包含一个整数，表示对应的结果。

样例

6
1 2 3 4 5 6
5
2 1 4
1 1 6
2 1 4
3 1 3
4 1 3

4
6
2
11

数据规模与约定

• 对于 $30\%$ 的数据，$n,q \le 20$
• 对于 $60\%$ 的数据，$n,q \le 2000$
• 对于 $100\%$ 的数据，$1 \le n,q \le 2 \times 10^5; 1 \le a_i,x \le 10^9; 1 \le p \le n; 1 \le l \le r \le n$