После каждой поездки пассажир ставит таксисту целую оценку от одного до пяти. Сервис такси рассчитывает по этим оценкам рейтинг водителя. Чтобы рейтинг отражал его недавнюю работу, старые поездки не учитываются.
Рейтинг на конец дня $$$d$$$ рассчитывается так:
Известны дни и оценки $$$n$$$ поездок. Поездки перечислены в порядке совершения, в том числе внутри одного дня. Также даны $$$q$$$ запросов: в каждом указан день, на конец которого нужно узнать рейтинг. Дни запросов перечислены от более ранних к более поздним и могут повторяться.
Для каждого запроса определите рейтинг таксиста после всех поездок указанного дня.
В первой строке находится целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 10^4$$$).
В первой строке каждого набора находятся четыре целых числа: $$$n$$$ — количество поездок, $$$q$$$ — количество запросов, $$$X$$$ — за сколько последних дней учитываются поездки, $$$Y$$$ — максимальное количество поездок в расчете рейтинга ($$$0 \le n \le 2\cdot 10^5$$$; $$$1 \le q, Y \le 2\cdot 10^5$$$; $$$1 \le X \le 10^9$$$).
В каждой из следующих $$$n$$$ строк находятся целые числа $$$d_i$$$ и $$$a_i$$$ — день и оценка $$$i$$$-й поездки ($$$1 \le d_i \le 10^9$$$; $$$1 \le a_i \le 5$$$). Поездки перечислены в порядке совершения: $$$d_1 \le d_2 \le \ldots \le d_n$$$. Порядок строк с одинаковым днем соответствует порядку поездок в этот день.
В каждой из следующих $$$q$$$ строк находится целое число $$$b_j$$$ — день $$$j$$$-го запроса ($$$1 \le b_j \le 10^9$$$). Запросы перечислены в порядке неубывания номера дня: $$$b_1 \le b_2 \le \ldots \le b_q$$$.
Гарантируется, что сумма значений $$$n+q$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите ответы на все $$$q$$$ запросов в том же порядке, в котором они даны. Каждый ответ выводите в отдельной строке.
Ответ считается правильным, если его абсолютная или относительная погрешность не превышает $$$10^{-6}$$$. Формально, если ваш ответ равен $$$v$$$, а правильный ответ равен $$$u$$$, должно выполняться неравенство $$$|v-u| \le 10^{-6}\cdot\max(1, |u|)$$$.
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
В первом наборе $$$X=2$$$ и $$$Y=3$$$: учитываются не более трех последних поездок за текущий и предыдущий дни.
В конце первого дня поездок еще нет, поэтому рейтинг равен нулю. В конце второго дня учитываются обе поездки этого дня, и рейтинг равен $$$(5+1)/2=3$$$.
В конце третьего дня за последние два дня накопилось пять поездок. Из них выбираются три последние, с оценками четыре, два и пять. Рейтинг равен $$$(4+2+5)/3=11/3$$$.
В конце седьмого дня учитываются поездки шестого и седьмого дней. Такая поездка только одна, с оценкой один. В конце восьмого дня учитываются уже седьмой и восьмой дни, в которые поездок не было. Поэтому рейтинг снова равен нулю.
Во втором наборе поездок нет.
| Название |
|---|


