CIRCSCR - Circles On A Screen

Yesterday Andrew wrote a program that draws n white circles on a black screen. The screen is monochrome and it has a resolution w x h pixels. Pixels are numbered from upper left corner (0, 0) to bottom right one (w-1, h-1).

A circle with the center at pixel (xc, yc) and the radius r consists of the pixels with coordinates (x, y) such that (xc-x)2 + (yc-y)2 <= r2 . If the circle does not fit on the screen, it is truncated. If some pixel belongs to two or more circles, it is white.

Example

The resulting picture was very nice, so Andrew decided to copy it to his wall. He has white wallpaper and he can only draw some parts of wall into black. Now he wants to know the amount of paint he needs.

He copies the picture exactly pixel-to-pixel, so you should write a program that calculates the number of black pixels left on a screen after drawing n circles.

Input

In the first line of input file there is an integer T, the number of test cases. T test cases follow.

Each test case begins with a line where there are three integers: w, h, and n (1 <= w, h <= 20.000; 1 <= n <= 100). Each of the following n lines contains descriptions of the circles. In i+1-th line there are three integers: xi, yi, ri (0 <= xi < w; 0 <= yi < h; 0 <= ri <= 40 000). They denote a circle with the center at pixel (xi, yi) and radius ri.

Output

For each test case you should output exactly one number - the number of black pixels left on the screen.

Example

Input:
2
5 3 2
1 1 1
3 1 1
12 9 2
3 3 2
7 5 4

Output:
6
51

Note: The picture corresponds to the second test case of the example.


Added by:Fidel Schaposnik
Date:2011-01-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC 2009, NEERC, Northern Subregional Contest

hide comments
2011-02-04 21:17:04 Fidel Schaposnik
@fake: you seem to be trying to allocate an array of 20000 times 20000 longs, which is way beyond the allowed memory limit, so this is probably why you're getting SIGKILL. you should try to think of a better algorithm, both in terms of running time and memory needed...
2011-01-26 20:54:36 askifpermit
please explain what is SIGKILL error.....
2011-01-24 16:18:11 Fidel Schaposnik
that 6 is the output for the first test case, which was copied there by mistake. i'm really sorry! it's been corrected now...
2011-01-24 16:18:11 LeppyR64
The 6 in the input is from his testing in the console. He just copied and pasted and forgot to remove the 6.
2011-01-24 16:18:11 hosam samy
what does 6 in the input refer to ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.