lqybzx 在动态规划方面很弱。有一天，他的室友给了他一个序列 $b_1, b_2, \dots, b_m$，并要求他进行动态规划。共有 $(m + 1)^2$ 个状态 $dp[i][j]$，其中 $0 \le i, j \le m$，转移方程为：

$$ dp[i][j] = \begin{cases} 0 & (i = 0) \\ i^2 + dp[i - 1][j] & (i > 0, j = 0) \\ i^2 + \max(dp[i - 1][j], dp[i - 1][j - 1] + b[i]) & (i > 0, j > 0) \end{cases} $$

lqybzx 无法解决这个简单的动态规划问题，所以他向你寻求帮助。给定一个序列 $a_1, a_2, \dots, a_n$ 和 $q$ 次询问。在第 $i$ 次询问中，给定三个整数 $l_i, r_i$ 和 $k_i$。请编写一个程序，计算当 lqybzx 的室友选择 $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ 作为初始序列 $b$ 时，$dp[m_i][k_i]$ 的值。其中 $m_i = r_i - l_i + 1$，且对于满足 $1 \le j \le m_i$ 的每个 $j$，都有 $b_j = a_{l_i+j-1}$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示序列的长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le i \le n, 1 \le a_i \le 10^6$)。第三行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示询问的数量。接下来的 $q$ 行，每行包含三个整数 $l_i, r_i$ 和 $k_i$ ($1 \le i \le q, 1 \le l_i \le r_i \le n, 1 \le k_i \le r_i - l_i + 1$)，表示一次询问。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$，且所有测试用例中 $q$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，打印 $q$ 行，其中第 $i$ ($1 \le i \le q$) 行包含一个整数，即 $dp[m_i][k_i]$ 的值。

样例

输入 1

1
5
1 2 3 4 5
3
1 3 2
1 5 5
3 3 1

输出 1

19
70
4