题目内容

给定一个长度为 $n$ 的整数序列

以及两个正整数步长 $p$ 与 $q$。

从任意起点下标 $i$（$1\le i\le n$）出发，并选择首步使用的步长是 $p$ 或者 $q$。随后沿着下标递增的方向行进，步长在 $p$ 与 $q$ 之间交替进行。

具体来说：

• 如果第一步选择步长 $p$，之后使用的步长依次为

  $$p,q,p,q,\ldots$$

• 如果第一步选择步长 $q$，之后使用的步长依次为

  $$q,p,q,p,\ldots$$

当下一步将使到达的下标超过 $n$ 时，路径立即终止，该步不会执行。

路径包含所有成功到达的下标，包括最初选择的起点。路径的价值定义为路径中所有下标所对应的 $A$ 值之和。

请计算在所有可能的起点以及首步选择中，交替步长路径能够获得的最大价值。

输入描述

每个测试文件包含多组测试数据。

第一行输入一个整数 $T$（$1\le T\le 10^5$），表示测试数据的组数。

对于每组测试数据：

第一行输入三个整数 $n,p,q$（$1\le n\le 2\times 10^5$，$1\le p,q\le n$），分别表示序列的长度和两个步长。

第二行输入 $n$ 个整数

其中

表示给定的整数序列。

保证单个测试文件中所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，新起一行输出一个整数，表示所有可能的起点和首步选择中，交替步长路径能够获得的最大价值。

样例

输入

3
5 1 2
1 2 3 4 5
6 2 3
5 -10 4 3 -2 8
4 2 2
-1 7 -3 5

输出

12
17
12