Big Brother needs a new machine that will keep track of all the people moving into town.
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:
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 ≤ x2′ and y1′≤ j ≤ y2′. This sum is also stored in c.
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).
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.