Водная монополия
От ужасной жары все водоёмы в прерии пересохли и остался только один родник, принадлежащий шаману воды Алекцачистлю. Родник приносит 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}.