IPSC Logo

Internet Problem Solving Contest

IPSC 2011

Problem G – Grid surveillance

Big Brother needs a new machine that will keep track of all the people moving into town.

Problem specification

The town is a grid G[0..4095][0..4095]. Initially, all entries in G are zeroes. The machine will need to support two types of instructions: additions and queries. Each addition modifies a single cell of the grid. Each query asks you about the sum of a rectangle. However, queries can also ask about older states of the grid, not only about the present one.

In order to have a smaller input file (and also in order to force you to process the instructions in the given order) we used the input format given below. There is a helper variable c, initially set to zero. Let φ(c,x) = (x xor c) mod 4096. The instructions are processed as follows:

Input specification

The first line of the input contains an integer r (1 r 100). The second line contains an integer q (1 q 20,000). Each of the next q lines contains one instruction. The sequence of instructions you should process is obtained by concatenating r copies of these q instructions.

Each instruction starts with its type z. If z = 1, we are doing an addition, so three integers x, y, a follow (0 x,y < 4096, 0 a 100). If z = 2, we are doing a query, so five integers x1, x2, y1, y2, t follow (0 x1,x2,y1,y2 < 4096, |t|≤ 500,000).

Output specification

For each query, output a single line with the appropriate answer.

In the hard data set, only submit the answers to the last 20,000 queries.

Example

input
2 5
1 2 2 3
1 2 4 1
2 1 5 1 5 -1
2 1 5 1 5 0
2 1 5 1 5 2
output
3
3
3
0
6
0