Description

At the beginning of the phalanx dance, everyone holds a screen with adjustable brightness and stands in an n × n matrix.

The initial brightness of all screens is 0.

There are two actions:

• 1 a s e: Dancers from s-th to e-th in column a will intermittently increase or decrease the screen brightness by 1, that is, s, s + 2, s + 4, ⋯ increase by 1, while s + 1, s + 3, s + 5, ⋯... turn down 1.

1. 2 a s e b: Dancers from s-th to e-th in column a move to the tail of column b.

For example:

We need to know the sum of the brightness of the columns with action.

Input

There are 5 test cases. For each case, the first line contains n m means the initial n × n square matrix and m actions.

Then following m lines describing the actions.

It is guaranteed that every action could be executed smoothly.

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ 10⁵

Output

For each action, output the total brightness of the relevant column.

Specifically: For action 1, output the total brightness of column a. For action 2, output the total brightness of column a and b separated by a space.

5 5
1 3 2 4
1 3 4 5
2 3 3 4 5
1 5 1 4
2 5 4 6 1

1
1
0 1
1
3 -2