Доставка вівса

Limits: 2 sec., 256 MiB

Зеник поїде до села купити мішок вівса на конеферму.

У селі є \(n\) хат, де продають овес. Хати розташовані на прямій дорозі та пронумеровані від \(1\) до \(n\) уздовж цієї дороги. Відстань між сусідніми хатами \(i\) та \(i+1\) дорівнює \(d_i\) метрів. В \(i\)-й хаті продають мішок вівса за \(c_i\) грн.

У селі їздять \(m\) маршруток, пронумерованих від \(1\) до \(m\). \(j\)-а маршрутка їздить між хатами \(u_j\) та \(v_j\) в обидва боки без проміжних зупинок. Квиток на неї коштує \(w_j\) грн.

Також у селі є кур’єр, що доставляє овес. Кур’єр може пересуватися селом пішки та маршрутками. До ціни доставки вівса включено вартість пересування кур’єра пішки — одна гривня за пройдений метр — а також ціни всіх квитків на маршрутки, якими їздив кур’єр. Коли кур’єр добирається від однієї хати до іншої, він вибирає спосіб, щоб ціна доставки була якнайменшою.

Зеник ще не вирішив, до якої хати він замовить доставку, щоб забрати товар фірою. Коли Зеник вирішить, куди замовляти доставку, то замовить він її з тої хати, звідки ціна за овес разом з доставкою буде найменшою.

Порахуйте для кожного \(i\) від \(1\) до \(n\), у скільки Зеникові обійдеться овес разом з доставкою до \(i\)-ї хати.

Input

У першому рядку задано ціле число \(n\) — кількість хат у селі, де продають овес.

У другому рядку записано \(n-1\) цілих чисел \(d_i\) — відстані між сусідніми хатами.

У третьому рядку задано \(n\) цілих чисел \(c_i\) — ціни вівса в хатах.

У четвертому рядку записано ціле число \(m\) — кількість маршруток у селі.

У наступних \(m\) рядках задано по три цілих числа \(u_j\), \(v_j\), \(w_j\), що описують маршрутки.

Output

В одному рядку виведіть \(n\) цілих чисел — для кожної хати \(i\) від \(1\) до \(n\) мінімальну ціну вівса разом з доставкою до \(i\)-ої хати.

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

Розгляньмо, як оптимально їхатиме кур’єр до хати з номером \(5\).

• Кур’єр купує овес у хаті з номером \(7\) за \(50\) грн.

• Кур’єр іде пішки \(11\) метрів від хати \(7\) до хати \(9\). За це йому треба заплатити \(11\) грн.

• Біля хати \(9\) кур’єр сідає на маршрутку до хати \(2\). Квиток на маршрутку коштує \(30\) грн.

• Кур’єр іде пішки \(47\) метрів від хати \(2\) до хати \(1\) — до ціни доставки додається \(47\) грн.

• Нарешті кур’єр їде маршруткою від хати \(1\) до хати \(5\) за \(10\) грн.

Загалом доставка вівса до хати з номером \(5\) обійдеться Зеникові в \(50+11+30+47+10=148\) (грн). Дешевше доставити овес до хати \(5\) не вийде.