You are given an array $$$a$$$ consisting of $$$n$$$ integers, as well as a parameter $$$k$$$ and an integer set $$$M=\{p, q\}$$$.

You can perform the following operation on $$$a$$$ an arbitrary number of times (possibly zero):

First, choose an interval $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$) of length at least $$$k$$$ (i.e., $$$r-l+1\ge k$$$) and an integer $$$m \in M$$$;
Then, set $$$a_i \gets a_i \bmod m$$$ for each $$$l \le i \le r$$$.

You have to find the minimum possible value of $$$\sum \limits_{i=1}^n a_i$$$ after all operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$p$$$, and $$$q$$$ ($$$1\le k\le n\le 10^5$$$, $$$1\le p \lt q\le 10^9$$$) — the length of $$$a$$$, the parameter, and the elements of $$$M$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a single integer — the minimum possible value of $$$\sum \limits_{i=1}^n a_i$$$ after all operations.

Note

In the second test case, a possible way to obtain $$$\sum \limits_{i=1}^n a_i=11$$$ is to apply the following operation to $$$a$$$:

Choose $$$[l,r]=[1,3]$$$ and $$$m=10$$$, then $$$a$$$ becomes $$$[1,1,9]$$$.

In the third test case, a possible way to obtain $$$\sum \limits_{i=1}^n a_i=3$$$ is to apply the following operations to $$$a$$$:

Choose $$$[l,r]=[1,4]$$$ and $$$m=4$$$, then $$$a$$$ becomes $$$[1,2,3,0]$$$;
Choose $$$[l,r]=[2,4]$$$ and $$$m=3$$$, then $$$a$$$ becomes $$$[1,2,0,0]$$$.

Interval Mod

Examples