题目内容

ByteCity 的通信网络由 $n$ 座信号塔和 $n-1$ 条光纤组成，任意两座信号塔之间存在唯一的通信路径。初始时，第 $i$ 座信号塔具有基础信号强度 $a_i$。

工程师计划进行 $q$ 次信号增强测试。每次测试指定两个信号塔 $u$ 和 $v$，以及一个基数 $x$。测试时，从塔 $u$ 出发，沿唯一路径依次经过中间的信号塔，直至塔 $v$。路径上出现的信号塔依次获得额外增益：第 $1$ 个塔（即 $u$）增益 $x$，第 $2$ 个塔增益 $x+1$，第 $3$ 个塔增益 $x+2$，……，最后一个塔（即 $v$）增益 $x+L$，其中 $L$ 为该路径经过的光纤数量（即路径长度）。

请你在所有测试完成后，计算每座信号塔最终的总信号强度（初始强度加上所有增益）。

约束条件：信号塔数量 $n$ 和测试次数 $q$ 均不超过 $10^5$；所有初始信号强度 $a_i$ 和每次测试的基数 $x$ 均为不超过 $10^6$ 的正整数。

输入描述