От ужасной жары все водоёмы в прерии пересохли и остался только один родник, принадлежащий шаману воды Алекцачистлю. Родник приносит \textbf{w} кувшинов воды в сутки, но пересохнет ровно через \textbf{d} дней, поэтому вожди хотят запастись как можно большим количеством воды. Алекцачистль согласен делиться водой только с вождями, которые принесут ему ценные ритуальные ракушки. Между ними он ежедневно распределяет воду пропорционально количеству ракушек, принесённых шаману с момента начала засухи (при этом может получиться нецелое число кувшинов). Утром каждого дня Алекцачистль принимает вождей, несущих ему ракушки, и пересчитывает объём воды, который достанется каждому из вождей в этот день. Если Алекцачистлю ещё никто не принёс ни одной ракушки, то в этот день всю воду он выпивает сам. \InputFile Первая строка входного файла содержит \textbf{4} целых числа: \textbf{n} - количество вождей, \textbf{m} - количество мешочков с ракушками, суммарно уплаченных Алекцачистлю, \textbf{d} - число дней функционирования родника, \textbf{w} - количество кувшинов воды, которые приносит родник за сутки. \textbf{1} ≤ \textbf{n}, \textbf{d} ≤ \textbf{100000}, \textbf{0} ≤ \textbf{m} ≤ \textbf{100000}, \textbf{1} ≤ \textbf{w} ≤ \textbf{1000}. Следующие \textbf{m} строк содержат по три числа: \textbf{d_i}, \textbf{h_i}, \textbf{p_i}, описывающие мешочки, поднесённые Алекцачистлю. Числа в \textbf{i}-й строке означают, что \textbf{h_i}-й вождь в \textbf{d_i}-й день отдал в \textbf{i}-м мешочке \textbf{p_i} ракушек. \textbf{1} ≤ \textbf{d_i} ≤ \textbf{100000}, \textbf{1} ≤ \textbf{h_i} ≤ \textbf{n},\textbf{1} ≤ \textbf{p}_\{i \}≤ \textbf{100}. Мешочки упорядочены в порядке неубывания номера дня. За один день вождь мог приносить более одного мешочка. \OutputFile Выведите \textbf{n} чисел - количество воды, накопленной вождями (с \textbf{1}-го по \textbf{n}-го) с абсолютной или относительной погрешностью не более \textbf{10^\{-6\}}.