테이블 위에는 $n$ 개의 블록 더미가 나란히 놓여 있으며, $i$ ($1 \le i \le n$) 번째 더미의 초기 블록 개수는 $a_i$입니다.

소 T와 소 S는 각각 망의 크기가 $p, q$인 마법의 체를 제공했습니다. 이 체를 사용하면 덮여 있는 블록 더미의 개수를 해당 모듈로(modulo) 값으로 나누어 나머지를 취함으로써 블록을 대량으로 제거할 수 있습니다. 자연스럽게 펼쳤을 때, 이 두 체는 정확히 $k$ 개의 블록 더미 너비를 덮습니다. 체는 특수한 탄성이 있어 양 끝으로 자유롭게 늘려 더 넓은 범위를 덮을 수 있지만, 안쪽으로 압축할 수는 없습니다. 마법의 체 사용 방법은 다음과 같습니다.

• 길이가 최소 $k$ 이상인 연속된 블록 구간 $[l, r]$을 선택하고 체를 덮습니다.
• 두 마법의 체 중 하나를 선택합니다. 즉, $m \in \{p, q\}$를 선택합니다.
• 구간 $[l, r]$ 내의 각 블록 더미에 대해, 해당 개수를 $m$으로 나눈 나머지로 바꿉니다. 즉, $a_i \leftarrow a_i \pmod m$을 수행합니다.

이 게임에 참여한 당신은 평범한 성적에 만족하지 않습니다. 순위표에서 최고가 되기 위해, 마법의 체를 임의의 횟수만큼 반복해서 사용하여 테이블 위에 남은 블록의 총합(즉, $\sum_{i=1}^n a_i$)을 최소 얼마까지 줄일 수 있는지 알고 싶습니다.

입력

각 테스트 케이스는 여러 개의 테스트 데이터로 구성됩니다. 입력의 첫 번째 줄에는 데이터의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^3$)가 주어집니다. 각 테스트 데이터에 대하여:

• 첫 번째 줄에는 네 개의 정수 $n, k, p, q$ ($1 \le k \le n \le 10^5, 1 \le p < q \le 10^9$)가 주어지며, 각각 블록 더미의 개수, 체가 자연스럽게 펼쳐졌을 때 덮는 블록 더미의 개수, 그리고 두 마법 체의 망 크기를 나타냅니다.
• 두 번째 줄에는 $n$ 개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)이 주어지며, 각 블록 더미의 초기 개수를 나타냅니다.

모든 테스트 데이터에서 $n$의 합은 $10^5$를 넘지 않습니다.

출력

각 테스트 데이터마다 테이블 위에 남은 블록 총 개수의 최솟값을 한 줄에 출력합니다.

예제

입력 1

6
1 1 3 4
2 0 2 6
3 2 10 20
3 1 4 1 59
4 3 3 4
1 2 3 4
6 4 9 20
18 27 180 9 45 99
7 4 3 5
6 7 14 12 100 78 4
9 4 244 353
9982 4435 3998 2443 5399 8244 3539 9824 4353

출력 1

1
11
3
0
4
569

참고

두 번째 테스트 데이터의 경우, 테이블 위 남은 블록 총합을 최솟값 11로 만드는 조작 방식은 다음과 같습니다.

• 구간 $[1, 4]$를 선택하고 망 크기가 10인 마법의 체를 사용하면, 남은 블록 개수는 $[1, 1, 9]$가 됩니다.

세 번째 테스트 데이터의 경우, 테이블 위 남은 블록 총합을 최솟값 3으로 만드는 조작 방식은 다음과 같습니다.

• 구간 $[2, 4]$를 선택하고 망 크기가 4인 마법의 체를 사용하면, 남은 블록 개수는 $[1, 2, 3, 0]$이 됩니다.
• 구간 $[1, 3]$을 선택하고 망 크기가 3인 마법의 체를 사용하면, 남은 블록 개수는 $[1, 2, 0, 0]$이 됩니다.