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

加权连续段

题目描述

给定一个长度为 $n$ 的整数数组 $a$，以及一个整数 $k$。

你需要从数组中选择一个非空连续子数组 $[l,r]$，其中 $1 \le l \le r \le n$。

设这个连续子数组的元素和为：

设这个连续子数组中所有元素绝对值的最大公约数为：

这个连续子数组的得分定义为：

请你求出所有非空连续子数组中的最大得分。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行输入两个整数 $n,k$，表示数组长度和参数 $k$。

第二行输入 $n$ 个非零整数 $a_1,a_2,\ldots,a_n$，表示数组中的元素。

数据范围

对于所有测试数据，满足：

• $1 \le T \le 2 \times 10^4$
• $1 \le n \le 2 \times 10^5$
• 所有测试数据的 $n$ 之和不超过 $2 \times 10^5$
• $0 \le k \le 10^9$
• $-10^9 \le a_i \le 10^9$
• $a_i \ne 0$

保证最终答案在 $64$ 位有符号整数范围内。

输出格式

对于每组测试数据，输出一行一个整数，表示所有非空连续子数组中的最大得分。

输入输出样例 #1

输入 #1

7
5 1
6 -4 10 -2 8
3 2
-5 -10 -15
3 5
12 18 6
4 1
8 -3 6 9
3 1
-6 1 1
6 0
-2 3 -1 4 -5 2
2 1000000000
1000000000 1000000000

输出 #1

20
15
108
21
3
6
1000000002000000000

说明/提示

对于第 $1$ 组数据，选择子数组 $[1,5]$，有：

因此得分为：

对于第 $2$ 组数据，必须选择非空连续子数组。选择子数组 $[3,3]$，有：

因此得分为：

对于第 $3$ 组数据，选择子数组 $[2,2]$，有：

因此得分为：

对于第 $4$ 组数据，选择子数组 $[1,4]$，有：

因此得分为：

对于第 $5$ 组数据，选择子数组 $[2,3]$，有：

因此得分为：

对于第 $6$ 组数据，$k=0$，选择子数组 $[2,4]$，有：

因此得分为 $6$。

第 $7$ 组数据的答案超过 $32$ 位整数范围，请使用 $64$ 位整数保存答案。