题目描述

给出一个长度为 $n$ 的正整数序列 $\{A_n\}$，维护 $q$ 个操作，操作有两种：

• 1 l r a b c：$\forall l \leq i \leq r, i \in \mathbb{N}$，令 $A_i$ 变为 $A_i + ai^2 + bi + c$；
• 2 l r：输出 $\min_{l \leq i \leq r} \{A_i\}$ 的值。

输入格式

第一行，两个整数 $n, q$，分别表示序列长度和操作个数。

第二行，$n$ 个整数 $A_1, A_2, \ldots, A_n$，表示序列。

接下来 $q$ 行，每行三到五个整数，描述操作。

输出格式

多行，每行一个整数，表示答案。

样例

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

13
55

数据范围与提示

对于 $100\%$ 的数据，$1 \leq n, q \leq 10^5$，$0 \leq A_i, c \leq 10^{13}$，$0 \leq b \leq 10^8$，$0 \leq a \leq 10^3$，$1 \leq l \leq r \leq n$。

本题采用子任务评测。对于同个子任务，你只有通过该子任务内的所有测试点，才能拿到该子任务的分数。

关于「数据有一定程度的随机」的解释：该子任务内所有数据由以下方式生成。

• 首先手动决定 $n, q, X, Y, Z$ 的值，其中 $1 \leq n, q \leq 10^5$，$0 \leq X \leq 10^3$，$0 \leq Y \leq 10^8$，$0 \leq Z \leq 10^{13}$。
• 任意 $a$ 均在 $[0, X]$ 范围内等概率随机生成，$b$ 在 $[0, Y]$ 范围内等概率随机生成，$A_i, c$ 在 $[0, Z]$ 范围内等概率随机生成。
• 对于操作中的区间参数 $l, r$，生成方式为：
  • 首先等概率随机生成整数 $k \in [1, n]$，表示区间长度；
  • 再等概率随机生成整数 $l \in [1, n - k + 1]$，表示区间的左端点；
  • 计算 $r = l + k - 1$，表示区间的右端点。

题目信息

• Idea / Std:
  https://loj.ac/user/1408
• Data:
  https://loj.ac/user/1408
  w](https://loj.ac/user/1206)
• Solution:
  https://loj.ac/user/10399
• Testing:
  https://loj.ac/user/10399
  https://loj.ac/user/1206)