Magic Stones Spell Processing

In this problem, you are given (N) magic stones, each with an initial magical charge. You are also provided with (M) spells that will be cast sequentially on these stones. There are two types of spells:

1. Update Spell: Formatted as 1 l r k. This spell increases the charge of every stone from index (l) to (r) (inclusive) by an amount (k).

2. Sum Spell: Formatted as 2 l r. This spell requires you to calculate and output the sum of the charges of stones from index (l) to (r) (inclusive).

Process each spell in the order given. For every Sum Spell, print the resulting sum on a new line.

All indices are 1-based. You can assume that the provided input is valid and fits the problem constraints.

inputFormat

The input is read from standard input and has the following format:

• The first line contains two integers (N) and (M): the number of stones and the number of spells, respectively.
• The second line contains (N) space-separated integers representing the initial charges of the stones.
• The next (M) lines each contain a spell in one of the following two formats:
  • 1 l r k: An update spell that increases the charge from stone (l) to stone (r) by (k).
  • 2 l r: A sum spell that asks for the sum of charges from stone (l) to stone (r).

outputFormat

For each Sum Spell (i.e. spells of the format 2 l r), output the sum of the charges of the stones from index (l) to (r) on a new line.## sample

5 5
10 20 30 40 50
2 1 5
1 2 4 10
2 1 5
1 1 2 5
2 1 3

150
180
90