Submit | All submissions | Best solutions | Back to list |

## HS12CHSH - Cherries Sharing |

Alice and Bob are trying to cut a rectangular cherry cake into two pieces.

They have agreed that:

- the partition must be done with a single, straight line cut parallel to one of the sides of the cake
- the cut should cross the center of mass of all cherries
- the number of cherries touched during the cut should be as small as possible

You have been asked to compute the parameters of the cut satisfying the above conditions. Simplify the problem assuming that each cherry is an ideal, homogeneous ball.

### Input

First, you are given *T*, the number of test cases (*T*<100). The test cases follow.
Each of the test cases consists of three positive integers: *w*, *l*, *c* denoting the width, the length and the number of cherries in the cake (*w*, *l* < 100 and *c*<10000).
In each of the next *c* lines the parameters of each successive cherry are given: *x*, *y* - the coordinates of the center), *m* - the mass of the cherry and *r* - the radius of the cherry (*x*<*w*, *y*<*l*, *m*, *r* <10).
Assume that the cake's vertices are: (0, 0), (*x*, 0), (*x*, *y*), (0, *y*).
The height of the cake and the vertical position of cherries have no impact on the cut parameters, hence they may be considered irrelevant and ignored.

### Output

For each of the test cases output in a separate line two characters: WE for a cut parallel to *x*-axis and NS for a cut parallel to *y*-axis
and one number - the cut offset with six digits of precision.

### Example

Input:2 31 71 5 10.5680 32.3080 8.0160 2.1860 15.9970 30.3860 2.7680 2.2490 3.6890 11.9840 7.9280 1.0350 6.5280 48.6800 5.7440 1.2970 23.5240 31.1280 9.6440 1.8320 69 36 5 15.0760 13.1800 5.9020 2.3240 33.5610 24.2980 7.9390 2.6720 27.4260 20.5670 2.5220 2.4220 38.7100 17.4060 1.7820 1.1920 20.8150 18.8790 9.0090 1.3320Output:NS 12.393005 NS 25.082539~~WE 29.850876 WE 19.284767~~

### Scoring

By solving this problem you score 10 points.

Added by: | kuszi |

Date: | 2013-02-14 |

Time limit: | 4s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM32-GCC ASM64 GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET |

Resource: | High School Programming League |