Oat Delivery

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk will go to the village to buy a bag of oats for the horse farm.

There are \(n\) houses in the village that sell oats. The houses are located on a straight road and are numbered from \(1\) to \(n\) along this road. The distance between adjacent houses \(i\) and \(i+1\) is \(d_i\) meters. The \(i\)-th house sells a bag of oats for \(c_i\) UAH.

There are \(m\) minibuses operating in the village, numbered from \(1\) to \(m\). The \(j\)-th minibus runs between houses \(u_j\) and \(v_j\) in both directions without intermediate stops. A ticket for it costs \(w_j\) UAH.

There is also a courier in the village who delivers oats. The courier can move around the village on foot and by minibuses. The delivery price of oats includes the cost of the courier’s movement on foot — one hryvnia per meter traveled — as well as the prices of all minibus tickets the courier used. When the courier gets from one house to another, they choose the route that minimizes the delivery price.

Zenyk has not yet decided to which house he will order the delivery to pick up the goods with a cart. When Zenyk decides where to order the delivery, he will order it from the house where the price of oats together with delivery is the lowest.

Calculate for each \(i\) from \(1\) to \(n\) how much oats together with delivery to the \(i\)-th house will cost Zenyk.

Input

The first line sets the integer \(n\) — the number of houses in the village that sell oats.

The second line contains \(n-1\) integers \(d_i\) — the distances between adjacent houses.

The third line specifies \(n\) integers \(c_i\) — the prices of oats in the houses.

The fourth line contains the integer \(m\) — the number of minibuses in the village.

The next \(m\) lines specify three integers \(u_j\), \(v_j\), \(w_j\) each, describing the minibuses.

Output

In a single line, print \(n\) integers — for each house \(i\) from \(1\) to \(n\), the minimum price of oats together with delivery to the \(i\)-th house.

Constraints

\(1 \le n \le 10^5\),

\(1 \le d_i \le 10^9\),

\(1 \le c_i \le 10^9\)

\(0 \le m \le 10^5\),

\(1 \le u_j < v_j \le n\),

\(1 \le w_j \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
10 47 74 80 747 474 100 4 7 11 500 500 450 470 800 300 50 600 900 100 2 2 9 30 1 5 10	138 91 165 245 148 150 50 54 61 72

Notes

Let’s consider how the courier will optimally travel to the house with number \(5\).

• The courier buys oats at the house with number \(7\) for \(50\) UAH.

• The courier walks \(11\) meters from house \(7\) to house \(9\). For this, they have to pay \(11\) UAH.

• Near house \(9\), the courier takes a minibus to house \(2\). The minibus ticket costs \(30\) UAH.

• The courier walks \(47\) meters from house \(2\) to house \(1\) — \(47\) UAH is added to the delivery price.

• Finally, the courier takes a minibus from house \(1\) to house \(5\) for \(10\) UAH.

In total, the delivery of oats to the house with number \(5\) will cost Zenyk \(50+11+30+47+10=148\) (UAH). It is not possible to deliver oats to house \(5\) cheaper.