A Difference Array Problem

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Java 2.5s
Python 2.5s
Memory limit: 512M

Author:
Problem type

You are given a $$2$$-dimensional grid of size $$N \times N$$, and $$Q$$ queries:

$$1\ x_1\ y_1\ x_2\ y_2\ v$$. This means adding $$v$$ to all elements in the subgrid starting at $$(x_1, y_1)$$ and ending at $$(x_2, y_2)$$. $$(-1\ 000 \le v \le 1\ 000, 1 \le x_1 \le x_2 \le N, 1 \le y_1 \le y_2 \le N)$$.

$$2\ x\ y$$. This query asks for the value of the element at position $$(x, y)$$. $$(1 \le x, y \le N)$$.

All elements in the grid start off at a value of $$0$$.

Input Specification

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

The next $$Q$$ lines will each contain a valid query as described above.

Output Specification

For each type $$2$$ query, output the value of the element at position $$(x, y)$$ on its own line.

$$N \le 100, Q \le 100$$

$$x_1 = x_2 = x = 1, N \le 1\ 000$$

No further constraints.

Sample Input

4 6
1 1 1 3 3 2
2 3 3
1 2 3 4 4 1
1 3 3 3 3 100
2 4 4
2 2 3

Sample Output

2
1
3