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