|
E |
Bulb
inside a Grid 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.
Switches come in two shapes and in various sizes. A switch can cover a rectangular or a square 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 that engulfs a square region is represented as (row, column, size) where (row, column) denotes the top-left corner and size denotes the size of the square.
A switch that engulfs a rectangular region is represented as (row, column, width, height) where (row, column) denotes the top-left corner 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 2 square switches; (4, 3, 2) and (5, 5, 4) and 1 rectangular switch; (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 and the number of times each switch is pressed, 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<50) that indicates the total number of test cases.
Each case starts with two integers N(0<N<108) and
M(0 ≤ M<50). 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 square-switch is formatted as (row, column, size) times where (1 ≤ row, column, size ≤ N) and (0 < times < 230). The meaning of (row, column, size) is given in the description and times represents the number of times that particular switch is pressed.
The information for a rectangle-switch is formatted as (row, column, width, height) times. Here (1 ≤ row, column, width, height ≤ N) and (0<times<230).
Output
For each case, print the case number followed by the total number of bulbs that are on after all the switches are pressed for the given number of times.
Note that the order in which the switches are pressed is extraneous for the final outcome and therefore its intentionally not stated.
Sample Input Output for
Sample Input
|
3 6
0 6
3 (4,
3, 2) - 1 (5,
5, 4) - 1 (2,
5, 3, 2) 1 1000
1 (1,
100, 5) 100 |
Case
1: 21 Case
2: 13 Case 3: 500500 |
Problem Setter: Sohel Hafiz
Special Thanks:
Note: Sample #2 is depicted in the figure given above.