Задача №115303. Отходы производства
Крупная промышленная компания управляет заводом, который производит важные товары, а отходы экологично утилизирует. Даже в те дни, когда заводы простаивают (что может случаться часто), доля отходов все равно утилизируется безопасным образом.
Известно, что заводы работали \(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}\).
В первом примере количество отходов будет меняться следующим образом:
- в первый день их \(0\);
- во второй день их станет \(0.5 \cdot 6 = 3\);
- в третий день их станет \(0.5 \cdot 3 + 0.5 \cdot 8 = 5.5\);
- в четвертый день их станет \(0.5 \cdot 5.5 + 0.5 \cdot 10 = 7.75\);
- в пятый день завод не производит ничего нового, и отходов становится \(0.5 \cdot 7.75 = 3.875\).
3 3 0.5 2 6 3 8 4 10 1 3 5
0.000000000000 5.500000000000 3.875000000000
5 6 0.3333333 1 27 6 27 3 27 4 27 5 27 1 2 3 4 5 6
8.999999100000 5.999999700000 12.999999100000 17.666665600000 20.777776755555 22.851850962963
1 1 0 1 1000000000 1000000000
0.000000000000