Statisticians like to create a lot of statistics. One simple measure is the mean value: the sum of all values divided by the number of values. Another is the median: the middle among all values when they have been sorted. If there are an even number of values, the mean of the two middle values will form the median.

These kinds of measures can be used for example to describe the population in a country or even some parts of the population in the country. Anne Jensen, Maria Virtanen, Jan Hansen, Erik Johansson and Jón Þórsson want to find a statistical measurement of how many statisticians there are in the Nordic countries. To be more precise, they want to find out how many statisticians there are per unit area. As the population in the Nordic countries are well spread out they will try the new measurement MAD, Median of All Densities. First put a square grid on the map. Then draw a rectangle aligned with the grid and calculate the density of statisticians in that area, i.e. the mean number of statisticians per area unit. After that, repeat the procedure until all possible rectangles have been covered. Finally the MAD is the median of all statistician densities.


The first line of the input contains of two space separated numbers $h$ and $w$ describing the height and width of the square grid, where $1 \leq h \leq 140$ and $1 \leq w \leq 120$. The next line contains two space separated numbers $a$ and $b$ which are the lower and upper bound of the allowed rectangle areas, i.e. $1 \leq a \leq rectangle area \leq b \leq w \times h$. Then there will follow $h$ lines with $w$ space separated numbers $s$ describing the number of statisticians in each square of the map, $0 \leq s \leq 10\, 000$. There will always exist a rectangle with an area in $[a,b]$.


The output contains of one line with the MAD. The number should be printed in number of statisticians per square and have absolute error at most $< 10^{-3}$.

Sample Input 1 Sample Output 1
4 2
1 8
6 5
2 5
2 9
7 13
Sample Input 2 Sample Output 2
2 3
2 4
6 1 4
2 7 1
CPU Time limit 4 seconds
Memory limit 1024 MB
Difficulty 7.5hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in