Sequence and Queries 19

Time limit2sMemory limit512 MB

Summary

Maintain an array under range add, range floor-division by d, and report the minimum and sum over a range. The division step needs a segment tree with min and sum.

Level: Hard8 of 10
Topics: Segment tree, Linked list, Math
Solved: No attempts yet

Problem

You are given a sequence $A_0, A_1, \dots, A_{n-1}$ of length $n$ . Write a program that processes the following four queries.

1 l r c: add $c$ to every $A_i$ with $l \le i \le r$ .
2 l r d: replace every $A_i$ with $l \le i \le r$ by $\lfloor A_i / d \rfloor$ .
3 l r: print the smallest value among the $A_i$ with $l \le i \le r$ .
4 l r: print the sum of the $A_i$ with $l \le i \le r$ .

$\lfloor x \rfloor$ is the largest integer that is at most $x$ . For example, $\lfloor -2.5 \rfloor = -3$ and $\lfloor -7 \rfloor = -7$ .

Input

The first line contains the length of the sequence $n$ and the number of queries $q$ . ( $1 \le n, q \le 100\,000$ )

The second line contains $A_0, A_1, \dots, A_{n-1}$ . ( $-10^9 \le A_i \le 10^9$ )

Each of the next $q$ lines contains one query. ( $0 \le l \le r \le n-1$ , $-10^4 \le c \le 10^4$ , $2 \le d \le 10^9$ )

Output

For every query of type 3 and every query of type 4, print the answer on its own line.

Examples2

Example 1

Input

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

Expected output

-2
-2
-2
-2
0
1
1

Example 2

Input

Expected output

-7
-7
-4
6