You are given a number $$$n$$$ and a number $$$m$$$ and an array $$$a$$$ of $$$n$$$ numbers and 2 types of queries. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $$$l, r, x$$$. You add all the numbers from $$$l$$$ to $$$r$$$(inclusive) by $$$x$$$. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}

2) Given 1 number $$$y$$$, output $$$a[y]$$$. This should be self explanatory.

At the end print the array $$$a$$$.

$$$m$$$ describes the number of queries being asked.

Example:

```
4 3
1 9 2 2
2 2 3
0 3 5
2
```

Output:

```
10
6 14 10 7
```

Should be less that $$$O(n^{2})$$$

Segment tree?

Isn't SegTree for finding the sum of numbers in a range? Am I stupid?

Yes, SegTrees are for that. For the first query just use Lazy Propagation, for the second your range is l = r = y.

Amazingly enough, you don't even need lazy propagation. You can just swap the logic in the update and query function. Update adds a value to a set of nodes, and query accumulates values as it moves down from the root to the leaf.

WOW! Thanks for sharing that!

Consider a segment tree on the "change in value" so we can use the so called "+1/-1 trick" and if we want to increment [L, R] by X, we can increment L by X and R+1 by -X