该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

染染船长，准备出发！

话虽然是这么说，但出发之前除了建设好整条船，还需要观察一下海面的情况，选择一个良辰吉日出海。

海面情况的一个重要指标就是海浪，尤其是其中很长的海浪。

为了能够量化这个问题，染染将本该连续的海面离散化成为了一个长度为 $n$ 的整数高度序列 $h_1, h_2, \cdots, h_n$，可以认为 $h_i$ 表示第 $i$ 块海面的波动高度。此时海浪可以定义为连续的海面 $h_l, h_{l+1}, \cdots, h_r$，满足存在实数基准高度 $h_B$，使得对于 $i = l+1, l+2, \cdots, r$ 都有：

染染现在会给出 $q$ 次询问，每次询问给出 $x, y$ 表示查询完全包含在连续的海面 $h_x, h_{x+1}, \cdots, h_y$ 内的最长海浪的长度。也就是说染染要找到海浪 $h_l, h_{l+1}, \cdots, h_r$ 使得 $x \leq l \leq r \leq y$ 并最大化 $r - l + 1$。

输入

本题单个测试点内包含多组测试数据。

输入第一行一个正整数 $T$ ($1 \leq T \leq 20$)，表示数据组数。

每组数据第一行两个正整数 $n, q$ ($1 \leq n, q \leq 10^5$)，表示海面被离散化后的序列长度和询问数量。

第二行 $n$ 个正整数 $h_1, h_2, \cdots, h_n$ ($-10^9 \leq h_i \leq 10^9$)，表示海面被离散化后的序列。

接下来 $q$ 行，第 $i$ 行包含两个正整数 $x, y$ ($1 \leq x \leq y \leq n$)，表示第 $i$ 次询问。

保证单个测试点内每组数据中 $n$ 的和与 $q$ 的和不超过 $10^6$。

输出

为了避免输出量过大，输出对每组数据进行压缩。

对于每组数据，假设染染第 $i$ 次询问的答案为 $r_i$，你只需要输出一行一个压缩后的非负整数 $R$： $R = (\sum_{i=1}^{q} i \cdot r_i) \mod (10^9 + 7)$

样例

1
7 3
-1 1 -1 1 3 7 3
1 3
3 7
1 5

21

提示

第 $1$ 次询问的答案为 $3$，对应海浪 $h_1, h_2, h_3$ 即 $-1, 1, -1$。

第 $2$ 次询问的答案为 $3$，对应海浪 $h_5, h_6, h_7$ 即 $3, 7, 3$。

第 $3$ 次询问的答案为 $4$，对应海浪 $h_1, h_2, h_3, h_4$ 即 $-1, 1, -1, 1$。