Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Cutting Cake
Time Limit: 10000MSMemory Limit: 131072K
Total Submissions: 778Accepted: 215
Case Time Limit: 3000MS


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.


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.


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
sample output#2


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

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator