Trên bàn có $n$ đống khối xếp thành hàng, đống thứ $i$ ($1 \le i \le n$) có số lượng ban đầu là $a_i$.

Tiểu T và Tiểu S cung cấp hai loại lưới ma thuật với kích thước mắt lưới lần lượt là $p$ và $q$, có khả năng loại bỏ khối bằng cách lấy số dư của các đống khối bị bao phủ. Khi trải ra tự nhiên, cả hai loại lưới này đều bao phủ đúng $k$ đống khối. Chúng có độ đàn hồi đặc biệt, có thể kéo giãn tự do về hai phía để bao phủ phạm vi dài hơn, nhưng không thể thu nhỏ lại. Cách sử dụng lưới ma thuật như sau:

• Chọn một đoạn liên tiếp các đống khối $[l, r]$ có độ dài ít nhất là $k$ và trải lưới lên đó;
• Chọn một trong hai loại lưới ma thuật, tức là chọn $m \in \{p, q\}$;
• Với mỗi đống khối trong đoạn $[l, r]$, thay thế số lượng khối của nó bằng số dư khi chia cho $m$, tức là $a_i \leftarrow a_i \pmod m$.

Vì đã tham gia trò chơi này, bạn chắc chắn không hài lòng với kết quả tầm thường. Để đạt thứ hạng cao nhất trên bảng xếp hạng, bạn muốn biết sau khi sử dụng lưới ma thuật bất kỳ số lần nào, tổng số khối còn lại trên bàn (tức là $\sum_{i=1}^n a_i$) có thể giảm xuống tối thiểu là bao nhiêu?

Dữ liệu vào

Mỗi bài kiểm tra bao gồm nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên dương $T$ ($1 \le T \le 10^3$), biểu thị số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa bốn số nguyên dương $n, k, p, q$ ($1 \le k \le n \le 10^5$, $1 \le p < q \le 10^9$), lần lượt biểu thị số đống khối, số đống khối mà lưới bao phủ khi trải tự nhiên, và kích thước mắt lưới của hai loại lưới ma thuật.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), biểu thị số lượng khối ban đầu của mỗi đống.

Đảm bảo tổng $n$ trong tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên không âm, biểu thị giá trị nhỏ nhất của tổng số khối còn lại trên bàn.

Ví dụ

Dữ liệu vào 1

6
1 1 3 4
2
3 2 10 20
31 41 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

Dữ liệu ra 1

1
11
3
0
4
569

Ghi chú

Đối với bộ dữ liệu thứ hai, một cách thao tác để tổng số khối còn lại trên bàn đạt giá trị nhỏ nhất là 11 như sau:

• Chọn đoạn $[1, 4]$ và sử dụng lưới ma thuật có kích thước mắt lưới là 10, số lượng khối còn lại trở thành $[1, 1, 9]$.

Đối với bộ dữ liệu thứ ba, một cách thao tác để tổng số khối còn lại trên bàn đạt giá trị nhỏ nhất là 3 như sau:

• Chọn đoạn $[2, 4]$ và sử dụng lưới ma thuật có kích thước mắt lưới là 4, số lượng khối còn lại trở thành $[1, 2, 3, 0]$;
• Chọn đoạn $[1, 3]$ và sử dụng lưới ma thuật có kích thước mắt lưới là 3, số lượng khối còn lại trở thành $[1, 2, 0, 0]$.