# Internet Problem Solving Contest

## 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:

• Each addition is described by three integers x, y, a. To process it, first compute the new coordinates x= φ(c,x) and y= φ(c,y). Then, add a to the cell G[x][y]. Finally, set c to the current value of G[x][y].
• Each query is described by five integers x1, x2, y1, y2, t. To process it, first compute the new coordinates xi= φ(c,xi) and yi= φ(c,yi). If necessary, swap them so that x1′≤ x2and y1′≤ y2.

Next, take the grid Gt that is defined as follows: If t = 0, then Gt = G. If t > 0, Gt is the state of G after the very first t additions. (If t exceeds the total number of additions so far, Gt = G.) Finally, if t < 0, then Gt is the state of G before the very last -t additions. (If -t exceeds the total number of additions so far, Gt is the initial state.)

The answer to the query is the sum of all Gt[i][j] where x1′≤ i x2and y1′≤ j y2. This sum is also stored in c.

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