eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Від жахливої жари усі водойми у прерії пересохли і залишилось лише одне джерело, яке належить шаману води Алекцачистлю. Джерело дає w кувшинів води на добу, але пересохне рівно через d днів, тому вожді хочуть запастись якомога більшою кількістю води.

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

Вранці кожного дня Алекцачистль приймає вождів, які несуть йому ракушки, і перераховує об'єм води, який дістанеться кожному з вождів у цей день. Якщо Алекцачистлю ще ніхто не приніс жодної ракушки, то у цей день усю воду він випиває сам.

Вхідні дані

Перший рядок вхідного файлу містить 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.

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

Вихідні дані

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

Приклад

Вхідні дані #1
2 3 3 1
1 1 1
1 2 2
2 1 2
Вихідні дані #1
0.933333333333333333
1.06666666666666667