K. Отходы производства
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Крупная промышленная компания управляет заводом, который производит важные товары, а отходы экологично утилизирует. Даже в те дни, когда заводы простаивают (что может случаться часто), доля отходов все равно утилизируется безопасным образом.

Известно, что заводы работали $$$n$$$ дней, $$$i$$$-й из этих дней был $$$d_i$$$-м производственным днем от начала работы компании, в этот день было использовано $$$w_i$$$ сырья для производства. В остальные дни завод простаивал, будем считать, что использовалось $$$0$$$ сырья.

Производство и утилизация параметризованы коэффициентом переработки сырья $$$r$$$. Чем он выше, тем быстрее происходит утилизация, но тем больше отходов производится при обработке сырья. Формально,

  • Если к концу некоторого дня на производстве ровно $$$x$$$ отходов, то в начале следующего дня их останется $$$x \cdot (1 - r)$$$.
  • Если в начале дня на производстве ровно $$$x$$$ отходов, то к концу дня их станет $$$x + w \cdot r$$$, где $$$w$$$ — количество использованного в этот день сырья.

Иными словами, если к концу дня $$$j - 1$$$ на производстве $$$x$$$ отходов, а в $$$j$$$-й день используется $$$w_j$$$ сырья, к концу $$$j$$$-го дня отходов станет $$$(1 - r)x + r w_j$$$. В начале самого первого дня отходов было $$$0$$$.

Cкоро на завод приедет инспекция. Инспекцию будет интересовать информация о количестве еще не утилизированных отходов в конце каких-то дней. К сожалению, эти записи были утеряны, поэтому руководство компании просит вас помочь с ответами на вопросы инспекции, имея данные о производстве.

Входные данные

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$m$$$ — количество дней, в которые производились новые отходы, и количество интересующих инспекцию дней, соответствие ($$$1 \le n, m \le 10^5$$$).

Во второй строке дано единственное вещественное число $$$r$$$ — коэффициент переработки сырья на производстве ($$$0 \le r \le 1$$$).

В $$$i$$$-й из следующих $$$n$$$ строк через пробел даны два целых числа $$$d_i$$$ и $$$w_i$$$ — очередной номер производственного дня и количество использованного в этот день сырья ($$$1 \le d_i, w_i \le 10^9$$$). Гарантируется, что все $$$d_i$$$ различны.

В последней строке через пробел перечислены $$$m$$$ целых чисел $$$q_i$$$ — номера дней, интересующих инспекцию ($$$1 \le q_i \le 10^9$$$).

Выходные данные

Выведите $$$m$$$ чисел, каждое в своей строке — количество отходов, хранящихся на фабрике в каждый из интересующих инспекцию дней.

Ваш ответ будет засчитан, если каждое из выведенных чисел имеет абсолютную или относительную ошибку не более $$$10^{-6}$$$.

Примеры
Входные данные
3 3
0.5
2 6
3 8
4 10
1 3 5
Выходные данные
0 5.5 3.875
Входные данные
5 6
0.3333333
1 27
6 27
3 27
4 27
5 27
1 2 3 4 5 6
Выходные данные
9 6 13 17.666666 20.777777 22.851851
Входные данные
1 1
0
1 1000000000
1000000000
Выходные данные
0
Примечание

В первом примере количество отходов будет меняться следующим образом:

  1. в первый день их $$$0$$$;
  2. во второй день их станет $$$0.5 \cdot 6 = 3$$$;
  3. в третий день их станет $$$0.5 \cdot 3 + 0.5 \cdot 8 = 5.5$$$;
  4. в четвертый день их станет $$$0.5 \cdot 5.5 + 0.5 \cdot 10 = 7.75$$$;
  5. в пятый день завод не производит ничего нового, и отходов становится $$$0.5 \cdot 7.75 = 3.875$$$.