Водяна монополія#4339
Від жахливої спеки всі водойми у прерії пересохли, і залишилося лише одне джерело, яке належить шаману води Алекцачистлю. Джерело дає кувшинів води на добу, але пересохне рівно через днів, тому вожді хочуть запастися якомога більшою кількістю води.
Алекцачистль згоден ділитися водою лише з вождями, які принесуть йому цінні ритуальні мушлі. Між ними він щоденно розподіляє воду пропорційно до кількості мушель, принесених шаману з моменту початку посухи (при цьому може вийти неціле число кувшинів).
Вранці кожного дня Алекцачистль приймає вождів, які несуть йому мушлі, і перераховує об'єм води, який дістанеться кожному з вождів у цей день. Якщо Алекцачистлю ще ніхто не приніс жодної мушлі, то у цей день усю воду він випиває сам.
Перший рядок вхідного файлу містить цілих числа: — кількість вождів, — кількість мішечків з мушлями, сумарно відданих Алекцачистлю, — число днів функціонування джерела, — кількість кувшинів води, які приносить джерело за добу. 1 \leq n, d \leq 100000, 0 \leq m \leq 100000, 1 \leq w \leq 1000.
Наступні рядків містять по три числа: d_i, h_i, p_i, які описують мішечки, піднесені Алекцачистлю. Числа у -му рядку означають, що h_i-й вождь у d_i-й день віддав у -му мішечку p_i мушель. 1 \leq d_i \leq 100000, 1 \leq h_i \leq n, 1 \leq p_i \leq 100.
Мішечки впорядковані у порядку неспадання номера дня. За один день вождь міг приносити більше одного мішечка.
Виведіть чисел — кількість води, накопиченої вождями (з -го по -й) з абсолютною чи відносною похибкою не більше 10^{-6}.
Приклад 1