eolymp
bolt
Try our new interface for solving problems
Məsələlər

Водная монополия

Водная монополия

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

От ужасной жары все водоёмы в прерии пересохли и остался только один родник, принадлежащий шаману воды Алекцачистлю. Родник приносит w кувшинов воды в сутки, но пересохнет ровно через d дней, поэтому вожди хотят запастись как можно большим количеством воды.

Алекцачистль согласен делиться водой только с вождями, которые принесут ему ценные ритуальные ракушки. Между ними он ежедневно распределяет воду пропорционально количеству ракушек, принесённых шаману с момента начала засухи (при этом может получиться нецелое число кувшинов).

Утром каждого дня Алекцачистль принимает вождей, несущих ему ракушки, и пересчитывает объём воды, который достанется каждому из вождей в этот день. Если Алекцачистлю ещё никто не принёс ни одной ракушки, то в этот день всю воду он выпивает сам.

Giriş verilənləri

Первая строка входного файла содержит 4 целых числа: n - количество вождей, m - количество мешочков с ракушками, суммарно уплаченных Алекцачистлю, d - число дней функционирования родника, w - количество кувшинов воды, которые приносит родник за сутки. 1n, d100000, 0m100000, 1w1000.

Следующие m строк содержат по три числа: d_i, h_i, p_i, описывающие мешочки, поднесённые Алекцачистлю. Числа в i-й строке означают, что h_i-й вождь в d_i-й день отдал в i-м мешочке p_i ракушек. 1d_i100000, 1h_in, 1p_{i }≤ 100.

Мешочки упорядочены в порядке неубывания номера дня. За один день вождь мог приносить более одного мешочка.

Çıxış verilənləri

Выведите n чисел - количество воды, накопленной вождями (с 1-го по n-го) с абсолютной или относительной погрешностью не более 10^{-6}.

Nümunə

Giriş verilənləri #1
2 3 3 1
1 1 1
1 2 2
2 1 2
Çıxış verilənləri #1
0.933333333333333333
1.06666666666666667