Su monopoliyası
Preriyadakı bütün su mənbələri dəhşətli istidən qurudu və yalnız su şamanı Alekçaxistlunun məxsus olduğu bir mənbə qaldı. Bu mənbə hər gün w küp su verir, lakin d gün sonra quruyacaq. Buna görə də, başçılar mümkün qədər çox su yığmaq istəyirlər.
Alekçaxistlu yalnız ona dəyərli ritual qabıqlar gətirən başçılarla suyu bölüşməyə razıdır. O, suyu hər gün quraqlığın başlanğıcından bəri şamana gətirilən qabıqların sayına mütənasib olaraq bölüşdürür (bu zaman tam küp sayı alınmaya bilər).
Hər gün səhər Alekçaxistlu ona qabıqlar gətirən başçıları qəbul edir və həmin gün hər bir başçıya düşən suyun həcmini hesablayır. Əgər Alekçaxistluya hələ heç kim qabıq gətirməyibsə, o gün bütün suyu özü içir.
Giriş verilənləri
Giriş faylının ilk sətiri 4 tam ədədi ehtiva edir: n - başçıların sayı, m - Alekçaxistluya ümumilikdə ödənilən qabıq torbalarının sayı, d - mənbənin işləmə günlərinin sayı, w - mənbənin gündə gətirdiyi su küplərinin sayı. 1 ≤ n, d ≤ 100000, 0 ≤ m ≤ 100000, 1 ≤ w ≤ 1000.
Növbəti m sətir hər biri üç ədəd ehtiva edir: d_i, h_i, p_i, Alekçaxistluya təqdim edilən torbaları təsvir edir. i-ci sətirdəki ədədlər d_i-ci gündə h_i-ci başçının i-ci torbada p_i qabıq verdiyini göstərir. 1 ≤ d_i ≤ 100000, 1 ≤ h_i ≤ n, 1 ≤ p_{i }≤ 100.
Torbalar gün nömrəsinin artma sırasına görə düzülüb. Bir gün ərzində başçı bir neçə torba gətirə bilərdi.
Çıxış verilənləri
n ədəd çıxarın - başçılar tərəfindən toplanan suyun miqdarı (birinci başçıdan n-ci başçıya qədər) mütləq və ya nisbi səhvi 10^{-6}-dan çox olmayaraq.