Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Cutting Cake
 Time Limit: 10000MS Memory Limit: 131072K Total Submissions: 778 Accepted: 215 Case Time Limit: 3000MS

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 x1, y1, x2, y2 (1 <= x1 <= x2 <= N, 1 <= y1 <= y2 <= 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

```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

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

Source

[Submit]   [Go Back]   [Status]   [Discuss]