A Difference Array Problem

View as PDF

Submit solution

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.

Subtasks

Subtask 1 [10%]

N \le 100, Q \le 100

Subtask 2 [30%]

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

Subtask 3 [60%]

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

Comments