Given n 2-dimensional data objects or points in a cluster, we can define the centroid \((x_0, y_0),\) radius R and diameter D of the cluster as follows.
\(x_0 = \frac{\sum\limits_{i=1}^{n}x_i}{n}, y_0 = \frac{\sum\limits_{i=1}^{n}y_i}{n}\)
\(R = \sqrt{\frac{\sum\limits_{i=1}^{n}(x_i - x_0)^2 + (y_i - y_0)^2}{n}}\)
\(D = \sqrt{\frac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(x_i - x_j)^2 + (y_i - y_j)^2}{n(n-1)}}\)
where R is the average distance from member objects to the centroid, and D is the average pairwise distance within the cluster. Both R and D reflect the tightness of the cluster around the centroid.
Note: Take \(R = 0\) for \(n \lt 1,\) and \(D = 0\) for \(n \lt 2\)
Given p data objects or points, you are supposed to answer q queries. In the \(i^{th}\) query, you consider only the points whose x-coordinate lies in \([x_{1i}, x_{2i}]\) and y-coordinate lies in \([y_{1i}, y_{2i}]\) as a single cluster. For each query you have to find the centroid, radius and diameter of the cluster. Since the values can be non-integer, you have to print the value of \(nx_0 + ny_0 + n^2R^2 + n(n-1)D^2\)
Constraints
- \(1 \le p, q \le 15 \times 10^4\)
- \(1 \le x_i, y_i\le 2 \times 10^4\)
- \(1 \le x_{1i} \le x_{2i} \le 2 \times 10^4\)
- \(1 \le y_{1i} \le y_{2i} \le 2 \times 10^4\)
Input Format
The first line contains two integers p and q denoting the number of data objects or points and the number of queries/clusters respectively.
Next p lines contains two-space separated integers denoting \(x_i\) and \(y_i\). The coordinates of \(i^{th}\) data point.
Next q line contains four space-separated integer denoting \(x_{1i}, x_{2i}, y_{1i}, \text{and } y_{2i}\) respectively.
Output Format
Output q lines each containing a single integer. \(i^{th}\) line denotes the value of \(nx_0 + ny_0 + n^2R^2 + n(n-1)D^2\) of the \(i^{th}\) cluster.