挖掘机是一种非常著名的机器。现在需要修筑一条长度为n米的公路，已知公路第i~(i+1)米内的海拔高度h_i（0<=i<n，1米范围内的微小起伏可以忽略），为了使公路尽量平整，可以用挖掘机对第l米到第r米之间的(r-l)个路段（1米长）进行一次挖掘操作，使这些路段的海拔都降低k米。已知项目负责人规划的m次挖掘操作，请求出操作后公路的平整度。

平整度定义为，各路段海拔高度与平均海拔高度之差的平方和。为了避免浮点误差，平均海拔向零的方向舍入到最近整数，例如2 4 5的平均数是3.6666667，我们将其舍入到3；-2 -4 -5的平均数是-3.6666667，我们将其舍入到-3。

数据范围：1<=n,m<=10⁵，0<=l<r<=n，|h_i|<=10⁴，1<=k<=10。

输入文件包含多组数据。

每组数据，第1行，一个整数n。
第2行，n个用空格分割的整数h₀,h₁,h₂,...,h_n-1。
第3行，一个整数m。
之后m行，每行3个整数l、r、k。

对于每组数据，输出1行，包含1个整数，表示公路的平整度。

XDOJ测试赛