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~ ~(1 \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