Water Monopoly
Due to the intense heat, all water sources in the prairie have dried up, except for one owned by the water shaman Alekzachistl. This source produces w jugs of water each day but will run dry after exactly d days. The chiefs aim to collect as much water as possible before it dries up.
Alekzachistl is willing to share the water only with chiefs who bring him valuable ritual shells. He distributes the water daily among the chiefs in proportion to the number of shells each has contributed since the drought began. This distribution may result in each chief receiving a non-integer number of jugs.
Every morning, Alekzachistl meets with the chiefs who bring shells and calculates how much water each will receive that day. If no shells have been brought to him by any chief, Alekzachistl consumes all the water himself for that day.
Input
The first line of the input contains 4 integers: n - the number of chiefs, m - the total number of bags of shells given to Alekzachistl, d - the number of days the water source will last, and w - the number of jugs of water the source provides daily. The constraints are 1 ≤ n, d ≤ 100000, 0 ≤ m ≤ 100000, 1 ≤ w ≤ 1000.
The next m lines each contain three integers: d_i, h_i, p_i. These numbers indicate that on the d_i-th day, the h_i-th chief gave p_i shells in the i-th bag. The constraints are 1 ≤ d_i ≤ 100000, 1 ≤ h_i ≤ n, 1 ≤ p_{i} ≤ 100.
The bags are listed in non-decreasing order based on the day number. A chief may bring multiple bags on the same day.
Output
Output n numbers, representing the amount of water each chief (from the 1-st to the n-th) has accumulated, with an absolute or relative error not exceeding 10^{-6}.