Description

Today, Fish gives QQ a cake for her birthday. The cake is unusual, and it looks like a square. The cake is made up of cream cells. The number of the cells is N * N. At first every cell is connected with 4 cells that are next to it.

Now, QQ wants to cut the cake. She has a special way to cut the cake. Every time, she will cut a rectangle from the cake. After this cut, the cells in the rectangle will be taken away. You know that some cells are connected as a piece of cake. Now Fish think it's a time to show how clever he is. As QQ's boy friend, he knows the size of the rectangle and where QQ will cut it each time. But it's a difficult job to calculate the number of the pieces QQ and Fish can take away after every cut. So Fish asks your help. As Fish's best friend, can you help the poor boy – Fish?

Take the following figure for example. In the figure, the grey cells have been taken away, while other cells are still in the cake. After this cut, which is drawn in the red rectangle, 4 pieces of cake will be taken away, which are the green one, the purple one, the yellow one and the blue one.

Input

The input consists of a single test case. The first line of input contains two positive integers N and M (1 <= N <= 1000, 1 <= M <= 10000), which are the size of cake and the numbers of cuts. The following M lines, each contains 4 integers x

₁

, y

₁

, x

₂

, y

₂

(1 <= x

₁

<= x

₂

<= N, 1 <= y

₁

<= y

₂

<= N), which are the coordinates of the top left cell and bottom right cell. The M rectangles are given in order.

Output

The output consists of m lines. Each line contains an integer, which is the number of the pieces QQ and Fish may take away after this cut.

sample input#1
3 2
1 2 3 2
2 1 2 3
sample input#2
3 5
1 2 1 2
2 2 2 2
2 1 2 1
3 3 3 3
1 1 3 3

sample output#1
1
2
sample output#2
1
1
1
1
3

Source

POJ Monthly--2006.06.25

, Chen Xue