Apparent Magnitude

Time Limit: 5000/3000 MS (Java/Others)

Memory Limit: 125536/65536 K (Java/Others)

Description

Every time when I gazing at the dazzling night sky, I wonder that how many stars are there and how bright they are …

From Wikipedia, I know that we can use a metric called apparent magnitude (apmag) to describe the brightness of a star. The apparent magnitude of a celestial body is a measure of its brightness as seen by an observer on Earth, normalized to the value it would have in the absence of the atmosphere. The brighter the object appears, the lower the value of its magnitude would be.
In this problem, can you help me to count the stars and their average apmag in the sky?

Input

There are several cases in the input, each case begin with two positive integer N (N<=60,000) and M (M<=20,000) giving the number of stars and queries. The following N lines give the 2D- coordinate (-10^8 < x, y < 10^8, integer) and the apmag (-40.00 < apmag < 40.00, a float number of two decimal places) of each star. After that, each of the following M lines contains four integers: -10^8 < lowX, lowY, upX, upY < 10^8, representing the lower-left and upper-right coordinates of a rectangle.

Output

For each query, you must answer the number of stars in the rectangle (including the boundary), and their apmag, as a format of "sum_apmag/number_star”. If there is no star in the rectangle, just print "0.00/0” in a single line.

Sample Input

4 2 1 1 1.24 2 2 4.56 3 3 7.89 4 4 3.21 1 1 2 2 5 6 7 8

Sample Output

5.80/2 0.00/0

Hint

chenyongfu

Source

2011 Multi-University Training Contest 6 -

提交代码