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
_{1}, x_{2}, y_{1}, y_{2}, 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_{1}′≤ x_{2}′ and y_{1}′≤ y_{2}′.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_{1}′≤ i ≤ x_{2}′ and y_{1}′≤ j ≤ y_{2}′. 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_{1}, x_{2}, y_{1}, y_{2}, t follow
(0 ≤ x_{1},x_{2},y_{1},y_{2} < 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

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

3

3

0

6

0