题目内容

给定序列 $A_1\ldots A_n$ 与步长 $p,q$。从任意起点 $i$ 出发，第一步选 $p$ 或 $q$，之后交替使用另一歩长，沿下标增大方向走，越界则停。路径价值和为经过下标的 $A$ 值之和。求所有起点与首步选择下的最大价值和。

$1 \le T \le 10^5$，$1 \le n \le 2\times 10^5$，$1 \le p,q \le n$，$-10^9 \le A_i \le 10^9$，所有 $n$ 之和不超过 $2\times 10^5$。

输入描述

第一行 $T$。每组第一行 $n,p,q$，第二行 $n$ 个整数 $A_i$。

输出描述

每组一行一个整数，表示最大路径价值和。

样例1

输入

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

说明

按题意模拟计算得到。