你玩過植物大戰殭屍嗎？

這是一款用植物打趴殭屍的熱門遊戲，已經紅了一段時間了。

在遊戲中，不同的植物可能相互作用，產生類似「合體技」的功能。這題的主要目標就是探討如何安排這些植物才能達到最大的攻擊力。為了簡化問題，我們只考慮只有一個殭屍以及田地只有一列的情況。

一列有$N$格的田地由左至右編號為 $0,1,\dots,N-1$，每格田地的肥沃度是 $a_i$ 。共有 $Q$ 個關卡，而且每一個關卡都只有一個殭屍，並且進行的場地（也就是你能種植物的地方）是$N$格田地中的某一個區間 $[L,R)$。而在每一關，你只有一個工具可以用：播種機。這是一個一次性道具，使用方法就是把他放在區間內最左邊的田地，之後他會開始往右開，並且在所經過的田地都種下一顆種子（含起點）。播種完（也就是超過編號 $R$ 的田地）之後，還會直接輾過殭屍造成一定的傷害。而對於某個已種下種子且肥沃度是 $a_i$ 的格子，過了一小段時間之後就會長出「特徵值」是 $a_i$ 的植物。所種出的植物會發動合體技，產生一顆種子子彈。這顆種子子彈所造成的威力是 $\sum k n_k^ 2$，其中 $n_k$ 代表擁有特徵值 $k$ 的植物個數。

對於給定的 $Q$ 個關卡，請計算播種機造成的傷害（不含輾過去的傷害）。