You are given a grid of size N × N . Each cell in the grid incorporates a bulb which can be initially on or off depending on its position. A bulb located at i-th row and j-th column will be initially off if i < j, otherwise it will be on. The following figure shows a grid of dimension 6 × 6 in its initial configuration. 100000 110000 111000 111100 111110 111111 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 × 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).
2/2 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. Note: Sample #2 is depicted in the figure given above. Sample Input 3 60 63 (4, 3, 2) - 1 (5, 5, 4) - 1 (2, 5, 3, 2) - 1 1000 1 (1, 100, 5) - 100 Sample Output Case 1: 21 Case 2: 13 Case 3: 500500