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 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 , initially set to zero. Let . The instructions are processed as follows: 

• Each addition is described by three integers x, y, a. To process it, first compute the new coordinates and . Then, add a to the cell . Finally, set c to the current value of .
• Each query is described by five integers . To process it, first compute the new coordinates and . If necessary, swap them so that and . Next, take the grid that is defined as follows: If t=0, then If , is the state of after the very first additions. (If t exceeds the total number of additions so far, .) Finally, if t < 0, then is the state of before the very last −t additions. (If −t exceeds the total number of additions so far, is the initial state.) The answer to the query is the sum of all where and . This sum is also stored in .

输入描述:

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  lines contains one instruction. The sequence of instructions you should process is obtained by concatenating  copies of these  instructions. 
Each instruction starts with its type . If , we are doing an addition, so three integers x, y, a follow (0 ≤ x,y < 4096, 0 ≤ a ≤ 100). If , we are doing a query, so five integers  follow .

输出描述:

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.

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

3 
3 
3 
0 
6 
0