描述

有n个小朋友需要接水，其中第i个小朋友接水需要ai分钟。

由于水龙头有限，小Hi需要知道如果为第l个到第r个小朋友分配一个水龙头，如何安排他们的接水顺序才能使得他们等待加接水的时间总和最小。

小Hi总共会有m次询问，你能帮助他解决这个问题吗？

假设3个小朋友接水的时间分别是2，3，4。如果他们依次接水，第一位小朋友等待加接水的时间是2，第二位小朋友是5，第三位小朋友是9。时间总和是16。

输入

第一行一个数T(T<=10)，表示数据组数

对于每一组数据：

第一行两个数n，m（1<=n,m<=20,000）

第二行n个数a1...an，表示每个小朋友接水所需时间(ai<=20,000)

接下来m行，每行两个数l和r

输出

对于每次询问，输出一行一个整数，表示答案。