挖掘机是一种非常著名的机器。现在需要修筑一条长度为n米的公路，已知公路第i~(i+1)米内的海拔高度h_i（0<=i

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

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

输入文件包含多组数据。

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

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

XDOJ测试赛