Internet Problem Solving Contest

• Easy input data set – G1
• Hard input data set – G2

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 x₁, x₂, y₁, y₂, t. To process it, first compute the new coordinates x_i′ = φ(c,x_i) and y_i′ = φ(c,y_i). If necessary, swap them so that x₁′≤ x₂′ and y₁′≤ y₂′.

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

  The answer to the query is the sum of all G_t[i][j] where x₁′≤ i ≤ x₂′ and y₁′≤ j ≤ y₂′. 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 x₁, x₂, y₁, y₂, t follow (0 ≤ x₁,x₂,y₁,y₂ < 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