Mario 在一家工厂工作。工厂里有一排 $n$ 根管道，从左到右依次编号为 $1, 2, 3, \dots, n$。对于 $i$ 从 $1$ 到 $n$，第 $i$ 根管道每秒输送 $a_i$ 单位的水。他的工作是打开一些连续的管道，使它们的总输出量恰好为每秒 $j$ 单位，但他不知道该怎么做。请帮助 Mario 找到应该打开哪一段管道。

给定 $a_1, a_2, a_3, \dots, a_n$。令 $s = \sum_{i=1}^n a_i$。你的任务是对于 $1$ 到 $s$ 之间的每个 $j$，找到一对 $(l_j, r_j)$，使得 $j = a_{l_j} + a_{l_j+1} + \dots + a_{r_j}$。根据老板的指令，如果对于某个 $j$ 存在 $k$ 种可能的 $(l, r)$，那么 $(l_j, r_j)$ 应为所有可能 $(l, r)$ 中第 $\lfloor \frac{k+1}{2} \rfloor$ 小的。如果对于某个 $j$ 不存在可能的 $(l, r)$，则 $(l_j, r_j) = (0, 0)$。

我们定义 $(x, y)$ 小于 $(z, w)$，当且仅当 $x < z$ 或者 ($x = z$ 且 $y < w$)。

例如，当 $n = 4$ 且 $(a_1, a_2, a_3, a_4) = (2, 1, 1, 2)$ 时，我们可以找到 $((l_1, r_1), (l_2, r_2), (l_3, r_3), (l_4, r_4), (l_5, r_5), (l_6, r_6)) = ((2, 2), (2, 3), (1, 2), (1, 3), (0, 0), (1, 4))$。

• 对于 $1$，有 $2$ 种可能的 $(l, r)$，即 $(2, 2), (3, 3)$，其中 $(l_1, r_1)$ 是第 $1$ 小的，所以 $(l_1, r_1) = (2, 2)$。
• 对于 $2$，有 $3$ 种可能的 $(l, r)$，即 $(1, 1), (2, 3), (4, 4)$，其中 $(l_2, r_2)$ 是第 $2$ 小的，所以 $(l_2, r_2) = (2, 3)$。
• 对于 $3$，有 $2$ 种可能的 $(l, r)$，即 $(1, 2), (3, 4)$，其中 $(l_3, r_3)$ 是第 $1$ 小的，所以 $(l_3, r_3) = (1, 2)$。
• 对于 $4$，有 $2$ 种可能的 $(l, r)$，即 $(1, 3), (2, 4)$，其中 $(l_4, r_4)$ 是第 $1$ 小的，所以 $(l_4, r_4) = (1, 3)$。
• 对于 $5$，不存在可能的 $(l, r)$，所以 $(l_5, r_5) = (0, 0)$。
• 对于 $6$，有 $1$ 种可能的 $(l, r)$，即 $(1, 4)$，其中 $(l_6, r_6)$ 是第 $1$ 小的，所以 $(l_6, r_6) = (1, 4)$。

输入格式

第一行包含一个整数 $t$，表示测试用例的总数。接下来的行描述每个测试用例。 每个测试用例的第一行包含一个整数 $n$，表示管道的数量。第二行包含 $n$ 个整数，表示 $a_1, a_2, a_3, \dots, a_n$。

• $1 \le t \le 20$
• $0 \le \min(a_i)$
• $1 \le \max(n, s) \le 30000$
• 最多有 $5$ 个测试用例满足 $\max(n, s) > 10000$。

输出格式

对于每个测试用例，在一行中输出两个整数：$\sum_{j=1}^s ((233)^j \times l_j) \pmod{10^9 + 7}$ 和 $\sum_{j=1}^s ((233)^j \times r_j) \pmod{10^9 + 7}$。

样例

样例输入 1

3
4
2 1 1 2
4
0 1 0 0
6
2 3 2 3 2 1

样例输出 1

685473415 769026629
233 932
811854151 883301517