Jim just had a party in his home and that’s why he painted some non overlapping beautiful circles in his floor. But after the party, Jim wants to repaint the floor, mostly the portions where the circles were drawn. As you know that painting for a party is exciting, but the repainting after the party is definitely boring; he bought an automatic Paint Brush from the departmental store for this task. The Paint Brush is a square shaped electronic brush and the size of its one side is k. It considers the room as a 2D plane. Initially it’s placed in the room. When turned on, it follows some pre-written moves that are programmed into its memory. And in each move, it moves k units North, South, West or East. The brush starts painting right after being turned on and continues painting until it stops. And it stops after finishing all the moves. The moves are programmed in such a way that it never paints the same part it has painted already. Now you are given the co-ordinates and radiuses of the circles and the lower left co-ordinates of the brush, its prewritten moves and k, you have to find the total percentage of the area of the circles that are repainted by the brush. All the co-ordinates are given according to the view of the brush. For example, in the above picture, the brush is initially placed on (1, 5) (red) and k is 4. One circle (green) was drawn whose center is on (10, 9) and radius is 3. And the instructions for the brush are (east 2, south 1). It means that it has 2 moves in east and 1 move in south. After 1 move in east it goes to (5, 5) (yellow). After 2-nd move to east it goes to (9, 5) (blue). And after 1 move to south it goes to (9, 1) (black). Input Input starts with an integer T (≤ 4000), denoting the number of test cases. Each test case starts with a line containing five integers n (1 ≤ n ≤ 16), Bx, By, k (1 ≤ k ≤ 20), and m (0 ≤ m ≤ 20000) where n denotes the number of non-overlapping circles, (Bx,By) denotes the lower-left corner of the initial position of the brush and m denotes the number of instructions. Each of the next n lines contains 3 integers xi, yi, ri (0 < ri ≤ 20000), where (xi,yi) denotes the center of the i-th circle and ri denotes the radius. Each of the next m lines will contain an instruction which is denoted by a string which shows the direction and is one of ”north”, ”south”, ”east”, ”west” and an integer p (1 ≤ p ≤ 20000) denoting the number of moves in this direction. |Bx|,|By|,|xi|,|yi| ≤ 20000 and the instructions are given such that it never paints any part more than once. You can assume that the total number of lines in the input file is less than 100000. Output For each case, print the case number and percentage of the area of the circles that are repainted by the Paint Brush. Print the percentage with at least 6 digits after the decimal point. Errors less than 10−5 will be ignored. See the samples for more details. Sample Input 2
2/2 11542 10 9 3 east 2 south 1 11543 10 9 3 east 2 north 1 west 1 Sample Output Case 1: 50.000000 Case 2: 100.000000