Maximizing Maritime Trade Profits

In the Age of Exploration, trading by sea was governed by a set of rigid rules. There are n main cities and m one‐directional shipping routes connecting these cities. A merchant ship carries an initial amount q of goods. Upon arriving at any city, the ship makes a trade with the city's leading merchant. In every such transaction the ship unloads a fixed fraction \(\frac{s}{s+t}\) of its current cargo. If the current cargo is \(p\) and the city’s rate is \(\text{mea}_i\), then the trade yields coins equal to \(p\times\frac{s}{s+t}\times \text{mea}_i\). After the trade, the remaining goods on board become \(p\times\frac{t}{s+t}\>.

After trading, the ship may choose to depart along one of the outbound shipping routes. For a shipping route with distance \(dis\), if the ship departs with cargo \(p\) then the voyage consumes \(p\times dis\) coins (as necessary expenditure) before the ship reaches the next city. The ship can then trade at the new city immediately using the same rule. Note that every time the ship reaches a city—even if the city is visited multiple times—the transaction happens at most once.

You are given two positive integers s and t, the number of cities n, the number of shipping routes m, and the initial cargo q. For each city, you are given its merchant rate \(\text{mea}_i\) (an integer). Then for each shipping route, you are given three integers: the starting city \(u\), the ending city \(v\), and the distance \(dis\) of the route. All cities are numbered from 1 to n, and the routes are one‐directional.

Let \(R=\frac{s}{s+t}\) and \(L=\frac{t}{s+t}\). If a ship starts at a city \(i\) with cargo \(q\) and follows a path \(i=i_0\to i_1\to\cdots\to i_k\), the total coins earned is computed as follows:

[ \text{coins} = q \times \Bigl( R,\text{mea}{i_0} + L\Bigl(R,\text{mea}{i_1} - dis_{(i_0\to i_1)}\Bigr) + L^2\Bigl(R,\text{mea}{i_2} - dis{(i_1\to i_2)}\Bigr) + \cdots + L^k \Bigl(R,\text{mea}{i_k} - dis{(i_{k-1}\to i_k)}\Bigr) \Bigr). ]

You may choose to stop your journey at any time (i.e. no further departures and no further trading beyond the current city). Given that you have an unlimited amount of time, determine for each city the maximum number of coins that can be earned if you start from that city. Note that all calculations follow the arithmetic of rational numbers, and the final answer may be fractional.

Input/Output formatting and examples are provided below.

inputFormat

The input is given in the following format:

s t
n m q
mea[1] mea[2] ... mea[n]
// then m lines follow
u v dis
u v dis
... (m lines total)

Here:

• s and t are two positive integers.
• n (number of cities) and m (number of routes) are positive integers.
• q is the initial amount of goods.
• mea[i] is the trading rate for city i (an integer).
• Each route is described by three integers: starting city u, ending city v (1-indexed), and dis (the distance of the route).

outputFormat

Output n numbers separated by spaces, where the i-th number is the maximum coins obtainable (as a real number) when starting from city i. Your answer will be considered correct if its absolute or relative error does not exceed 1e-6.

sample

1 1
2 1 10
10 20
1 2 5

75.000000 100.000000