## An Array Problem

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Given an array $$a$$ of length $$N$$, support $$Q$$ of the following operations:

• 1 l r v k Subtract $$v$$ from all elements $$i\ (l \le i \le r)$$ only if $$a_i > k$$.
• 2 l r k Sum up all elements $$i\ (l \le i \le r)$$ only if $$a_i > k$$.

$$1 \le l \le r \le N$$, $$0 \le v \le 10^3$$, and $$0 \le k \le 10^6$$.

#### Input Specification

The first line will contain two integers, $$N, Q\ (1 \le N, Q \le 10^3)$$.

The next line will contain $$N$$ integers, $$a_1, a_2, \ldots, a_N\ (0 \le a_i \le 10^6)$$.

The next $$Q$$ lines will each contain a valid operation as defined above.

#### Output Specification

For each type $$2$$ operation, print out the desired answer on its own line.

#### Sample Input

4 3
2 3 1 4
1 1 3 2 1
2 1 2 0
2 3 4 1

#### Sample Output

1
4