Water Monopoly#4339
Due to the terrible heat, all the bodies of water in the prairie have dried up, leaving only one spring, which belongs to the water shaman Alecchistl. The spring produces jugs of water per day, but it will dry up exactly after days, so the chiefs want to stockpile as much water as possible.
Alecchistl agrees to share water only with the chiefs who bring him valuable ritual shells. Each day, he distributes the water among them in proportion to the number of shells they have brought him since the beginning of the drought (which may result in a non-integer number of jugs).
Every morning, Alecchistl receives the chiefs as they bring him shells and recalculates the volume of water each chief will receive that day. If no one has yet brought Alecchistl any shells, he drinks all the water himself that day.
The first line of the input file contains integers: — the number of chiefs, — the total number of pouches of shells given to Alecchistl, — the number of days the spring will function, — the number of jugs of water the spring produces per day. 1 \leq n, d \leq 100000, 0 \leq m \leq 100000, 1 \leq w \leq 1000.
The next lines each contain three numbers: d_i, h_i, p_i, describing the pouches offered to Alecchistl. The numbers in the -th line mean that on day d_i, chief h_i gave p_i shells in the -th pouch. 1 \leq d_i \leq 100000, 1 \leq h_i \leq n, 1 \leq p_i \leq 100.
The pouches are given in non-decreasing order of the day. On a given day, a chief may bring more than one pouch.
Print numbers — the amount of water accumulated by the chiefs (from -st to -th), with absolute or relative error not exceeding 10^{-6}.
Example 1