你玩過植物大戰殭屍嗎？

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

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

一列有$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$個關卡，請計算播種機造成的傷害（不含輾過去的傷害）。

For Testdata: 0 ~ 4, Score: 7
For Testdata: 5 ~ 9, Score: 19
For Testdata: 10 ~ 14, Score: 37
For Testdata: 15 ~ 19, Score: 37