J. Taxi Driver Rating
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

After each ride, a passenger gives the taxi driver an integer rating from one to five. The taxi service calculates the driver's rating based on these ratings. To make the rating reflect recent performance, old rides are not taken into account.

The rating at the end of day $$$d$$$ is calculated as follows:

  1. Rides from the last $$$X$$$ days, including day $$$d$$$, are selected.
  2. If there are more than $$$Y$$$ selected rides, only the last $$$Y$$$ of them remain. Otherwise, all selected rides remain.
  3. The sum of the ratings of the remaining rides is divided by their number. If no rides remain, the rating is zero.

The days and ratings of $$$n$$$ rides are known. The rides are listed in the order they were made, including within the same day. There are also $$$q$$$ queries: each query specifies a day for which the rating at the end of that day must be found. The query days are listed in nondecreasing order and may repeat.

For each query, determine the taxi driver's rating after all rides of the specified day.

Input

The first line contains an integer $$$t$$$ — the number of test cases ($$$1 \le t \le 10^4$$$).

The first line of each test case contains four integers: $$$n$$$ — the number of rides, $$$q$$$ — the number of queries, $$$X$$$ — how many last days are taken into account, and $$$Y$$$ — the maximum number of rides used in the rating calculation ($$$0 \le n \le 2\cdot 10^5$$$; $$$1 \le q, Y \le 2\cdot 10^5$$$; $$$1 \le X \le 10^9$$$).

Each of the next $$$n$$$ lines contains two integers $$$d_i$$$ and $$$a_i$$$ — the day and the rating of the $$$i$$$-th ride ($$$1 \le d_i \le 10^9$$$; $$$1 \le a_i \le 5$$$). The rides are listed in the order they were made: $$$d_1 \le d_2 \le \ldots \le d_n$$$. The order of lines with the same day matches the order of rides on that day.

Each of the next $$$q$$$ lines contains an integer $$$b_j$$$ — the day of the $$$j$$$-th query ($$$1 \le b_j \le 10^9$$$). The queries are listed in nondecreasing order of day number: $$$b_1 \le b_2 \le \ldots \le b_q$$$.

It is guaranteed that the sum of $$$n+q$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output the answers to all $$$q$$$ queries in the same order as they are given. Print each answer on a separate line.

The answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, if your answer is $$$v$$$ and the correct answer is $$$u$$$, the inequality $$$|v-u| \le 10^{-6}\cdot\max(1, |u|)$$$ must hold.

Example
Input
2
6 5 2 3
2 5
2 1
3 4
3 2
3 5
6 1
1
2
3
7
8
0 1 2 3
1
Output
0.000000000
3.000000000
3.666666667
1.000000000
0.000000000
0.000000000
Note

In the first test case, $$$X=2$$$ and $$$Y=3$$$: at most the last three rides from the current and previous days are taken into account.

At the end of the first day, there are no rides yet, so the rating is zero. At the end of the second day, both rides of that day are taken into account, and the rating is $$$(5+1)/2=3$$$.

At the end of the third day, five rides have accumulated over the last two days. Among them, the last three are selected, with ratings four, two, and five. The rating is $$$(4+2+5)/3=11/3$$$.

At the end of the seventh day, rides from the sixth and seventh days are taken into account. There is only one such ride, with rating one. At the end of the eighth day, the sixth and seventh days are taken into account, but there were no rides on those days. Therefore, the rating is zero again.

In the second test case, there are no rides.