F

Bulb inside a Grid (II)

Input: Standard Input

Output: Standard Output

 

You are given a grid of size N x N. Each cell in the grid incorporates a bulb which can be initially on or off depending on its position. A bulb located at ith row and jth column will be initially off if i < j otherwise it will be on. The following figure shows a grid of dimension 6 x 6 in its initial configuration.

 

1 0 0 0 0 0

1 1 0 0 0 0

1 1 1 0 0 0

1 1 1 1 0 0

1 1 1 1 1 0

1 1 1 1 1 1

 

 

Here 1 indicates on state and 0 indicates off state.

A switch can cover a rectangular region in the grid.  A switch, when pressed, toggles all the bulbs in its corresponding region (that is, all the bulbs that are on goes off and vice versa).

A switch is represented by four integers (row, column, width, height) where (row, column) denotes the top-left corner of the rectangular region and width & height are self-explanatory.

Here is a diagram that should extricate things.

The diagram shows a grid of size 6 x 6 with 3 switches in action.

There are 3 switches; (4, 3, 2, 2), (5, 5, 4, 4) and (2, 5, 3, 2). Note that the regions wrap around and they can also overlap.

Given the dimension of the grid, the number of switches in action, can you find out the number of bulbs that are on at the end?

 

Input

The first line of input is an integer T(T ≤ 25) that indicates the total number of test cases.
Each case starts with two integers N(1 ≤ N ≤ 30,000) and M(1 ≤ M ≤ 30,000). N indicates the size of the grid and M specifies the total number of switches. Each of the following M lines gives the information of a switch.

 

The information for a switch is represented by four integer values row, column, width, height.  Here (1 ≤ row, column, width, height ≤ N).

                                                                                                                                                                                       

Output

For each case, print the case number followed by the total number of bulbs that are on after all the switches are pressed.

 

Note that the order in which the switches are pressed is extraneous for the final outcome and therefore it’s intentionally not stated.

 

Sample Input                               Output for Sample Input

3

6 0

6 3

4 3 2 2

5 5 4 4

2 5 3 2

1000 1

1 100 5 5

Case 1: 21

Case 2: 13

Case 3: 500525

Warning: Input file size is around 10 MB.

Problemsetter: Md. Arufuzzaman Arif

Special Thanks: Manzurur Rahman Khan, Sohel Hafiz