High School Programming League Problems Archive

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.3320

Output:
NS 12.393005
NS 25.082539
WE 29.850876
WE 19.284767

Scoring

By solving this problem you score 10 points.