染染船长，准备出发！
话虽然是这么说，但出发之前除了建设好整条船，还需要观察一下海面的情况，选择一个良辰吉日出海。
海面情况的一个重要指标就是海浪，尤其是其中很长的海浪。
为了能够量化这个问题，染染将本该连续的海面离散化成为了一个长度为 nn 的整数高度序列 h1,h2,⋯,hnh1,h2,⋯,hn，可以认为 hihi 表示第 ii 块海面的波动高度。此时海浪可以定义为连续的海面 hl,hl+1,⋯,hrhl,hl+1,⋯,hr，满足存在实数基准高度 hBhB，使得对于 i=l+1,l+2,⋯,ri=l+1,l+2,⋯,r 都有：(hi−1−hB)⋅(hi−hB)<0(hi−1−hB)⋅(hi−hB)<0
染染现在会给出 qq 次询问，每次询问给出 x,yx,y 表示查询完全包含在连续的海面 hx,hx+1,⋯,hyhx,hx+1,⋯,hy 内的最长海浪的长度。也就是说染染要找到海浪 hl,hl+1,⋯,hrhl,hl+1,⋯,hr 使得 x≤l≤r≤yx≤l≤r≤y 并最大化 r−l+1r−l+1。
本题单个测试点内包含多组测试数据。
输入第一行一个正整数 T (1≤T≤20)T (1≤T≤20)，表示数据组数。
每组数据第一行两个正整数 n,q (1≤n,q≤105)n,q (1≤n,q≤105)，表示海面被离散化后的序列长度。
第二行 nn 个正整数 h1,h2,⋯,hn (−109≤hi≤109)h1,h2,⋯,hn (−109≤hi≤109)，表示海面被离散化后的序列。
接下来 qq 行，第 ii 行包含两个正整数 x,y (1≤x≤y≤n)x,y (1≤x≤y≤n)，表示第 ii 次询问。
保证单个测试点内每组数据中 nn 的和与 qq 的和不超过 106106。
为了避免输出量过大，输出对每组数据进行压缩。
对于每组数据，假设染染第 ii 次询问的答案为 riri，你只需要输出一行一个压缩后的非负整数 RR：R=(∑i=1qi⋅ri)mod(109+7)R=(i=1∑qi⋅ri)mod(109+7)
1
7 3
-1 1 -1 1 3 7 3
1 3
3 7
1 521
第 11 次询问的答案为 33，对应海浪 h1,h2,h3h1,h2,h3 即 −1,1,−1−1,1,−1。
第 22 次询问的答案为 33，对应海浪 h5,h6,h7h5,h6,h7 即 3,7,33,7,3。
第 33 次询问的答案为 44，对应海浪 h1,h2,h3,h4h1,h2,h3,h4 即 −1,1,−1,1−1,1,−1,1。