In pattern recognition, the k-Nearest Neighbors algorithm (or k-NN for short) is a non-parametric method used for classification and regression. In both cases, the input consists of the k closest training examples in the feature space.
In k-NN regression, the output is the property value for the object. This value is the average of the values of its k nearest neighbors.
---Wikipedia
Today, kNN takes revenge on you, again. You have to handle a kNN case in one-dimensional coordinate system. There are N points with a position Xi and value Vi. Then there are M kNN queries for point with index i, recalculate its value by averaging the values its k-Nearest Neighbors. Note you have to replace the value of i-th point with the new calculated value. And if there is a tie while choosing k-Nearest Neighbor, choose the one with the minimal index first.
(Have you ever tried the problem “Revenge of kNN”? They are twin problems!)
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two integers N and M. Then N lines follows, each line contains two integers Xi and Vi. Then M lines with the queried index Qi and Ki follows, in which Ki indicating the number of k-Nearest Neighbors
[Technical Specification]
1. 1 <= T <= 5
2. 2 <= N <= 100 000
3. 1 <= M <= 100 000
4. 1 <= Vi <= 1 000
5. 1 <= Xi <= 1 000 000 000, and no two Xi are identical.
6. 1 <= Qi <= N
7. 1 <= Ki <= N - 1
For each test case, output sum of all queries rounded to three fractional digits.