This page is still under construction.

Parts of this page are still being built. What you see may change.

Mokia

Time limit1sMemory limit128 MB

Summary
Point updates add customers to grid cells and each query asks for the total inside a rectangle using only earlier updates.
Level

Hard8 of 10

Topics
Divide and conquer, Segment tree
Solved
No attempts yet

Problem

The Moldovan mobile phone company Mokia has built a new customer location system. Like other location systems it answers a query of the form "Where is customer C?" with millimeter precision, and it also answers a query of the form "How many customers are inside a given rectangular area?".

The system treats the world as a square of size W×WW \times W that is divided into cells of size 1×11 \times 1. A cell is named by a pair of indices (x,y)(x, y) with 1≤x,y≤W1 \le x, y \le W. Indexing starts at 1, so a table of size 4×44 \times 4 has 1≤x≤41 \le x \le 4 and 1≤y≤41 \le y \le 4.

Write a program that reports how many customers are inside a given rectangular area.

Input

Each instruction is on its own line and consists of one instruction integer followed by its parameters.

InstructionParametersMeaning
0WCreate a table of size W×WW \times W whose cells are all 0. This instruction is given once, as the first instruction.
1x y AAdd AA to the number of customers in cell (x,y)(x, y). AA is a positive integer.
2X1 Y1 X2 Y2Ask for the total number of customers in the cells (x,y)(x, y) with X1≤x≤X2X_1 \le x \le X_2 and Y1≤y≤Y2Y_1 \le y \le Y_2.
3noneStop the program. This instruction is given once, as the last instruction.

A query counts only the add instructions that come before it in the input. Print nothing for a line whose instruction is not 2.

Output

For every instruction 2, print the requested number of customers on its own line, in the order the queries are given.

Constraints

  • 1≤W≤2 000 0001 \le W \le 2\,000\,000
  • 1≤X1≤X2≤W1 \le X_1 \le X_2 \le W
  • 1≤Y1≤Y2≤W1 \le Y_1 \le Y_2 \le W
  • 1≤x,y≤W1 \le x, y \le W
  • 0<A≤10 0000 < A \le 10\,000
  • The number of instruction 1 lines is at most 160,000.
  • The number of instruction 2 lines is at most 10,000.

Examples2

  1. Example 1

    Input
    0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
    Expected output
    3
5

  2. Example 2

    Input
    0 1
2 1 1 1 1
1 1 1 5
2 1 1 1 1
1 1 1 7
2 1 1 1 1
3
    Expected output
    0
5
12