#4602. 「雅礼集训 2017 Day1」市场

「雅礼集训 2017 Day1」市场

Description

从前有一个贸易市场,在一位执政官到来之前都是非常繁荣的,自从他来了之后,发布了一系列奇怪的政令,导致贸易市场的衰落。

n n 个商贩,从 0n1 0 \sim n - 1 编号,每个商贩的商品有一个价格 ai a_i ,有两种政令;同时,有一个外乡的旅客想要了解贸易市场的信息,有两种询问方式:

  1. (政令)l,r,c l, r, c ,对于 i[l,r],aiai+c i \in [l, r], a_i \leftarrow a_i + c
  2. (政令)l,r,d l, r, d ,对于 $ i \in [l, r], a_i \leftarrow \lfloor {a_i}/{d} \rfloor $
  3. (询问)给定 l,r l, r ,求 mini[l,r]ai \min_{i \in [l, r]} a_i
  4. (询问)给定 l,r l, r ,求 i[l,r]ai \sum_{i\in [l, r]} a_i

Input

第一行为两个空格隔开的整数 n,q n, q 分别表示商贩个数和政令 + 询问个数。 第二行包含 n n 个由空格隔开的整数 a0an1 a_0 \sim a_{n - 1} 接下来 q q 行,每行表示一个操作,第一个数表示操作编号 14 1 \sim 4 ,接下来的输入和问题描述一致。

Output

对于每个 3、4 操作,输出询问答案。

Samples

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9
-2
-2
-2
-2
0
1
1

Limitation

对于 30% 30\% 的数据,n,q103 n, q \leq 10 ^ 3 ; 对于 60% 60\% 的数据,保证数据随机; 对于 100% 100\% 的数据,$ 1 \leq n, q \leq 10 ^ 5, 0 \leq l \leq r \leq n - 1, c \in [-10 ^ {4}, 10 ^ 4], d \in [2, 10 ^ 9] $