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:
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.
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$$$.
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.
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
0.000000000 3.000000000 3.666666667 1.000000000 0.000000000 0.000000000
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.