You have $n$ cards in front of you, and the $i$-th card from the left has a positive integer $A_i$ written on it.

You will choose a subset of these cards, keeping their relative order, to form a new sequence of cards.

Let this new sequence of cards have $m$ cards, where the number written on the $i$-th card is $B_i$.

The value of this card sequence is defined as:

$$ \sum \limits_{i=1}^{m-1}\lfloor \frac{S}{\textbf{LCM}(B_i,B_{i + 1})}\rfloor \times \textbf{LCM}(B_i,B_{i + 1}) $$

where $\textbf{LCM}(x,y)$ denotes the least common multiple of $x$ and $y$.

Your goal is to maximize this value.

For some test cases, you also need to solve the following problem:

Add a disabling rule: if the $i$-th card is disabled, the sequence of cards you choose cannot contain it.

You want to know: for $i=1 \dots n$, what is the maximum value of the card sequence you can choose if the $i$-th card is disabled? Let this be $ans_i$.

To reduce the output size, you only need to output $\bigoplus\limits_{i=1}^ni\times ans_i$.

Input

The first line contains four positive integers $n, S, tp, id$. The first two parameters are as described above, $tp=0/1$ indicates the type of the test case (see Output section for details), and $id$ is the subtask number.

The second line contains $n$ positive integers $A_1 \dots A_n$.

Output

• If $tp=0$, output a single integer representing the answer without any disabling rules.
• If $tp=1$, output two integers, representing the answer without any disabling rules and the value of $\bigoplus\limits_{i=1}^ni\times ans_i$ under the disabling rules, respectively.

Examples

Input 1

5 10 1 1
3 2 1 4 5

Output 1

26 18

Input 2

10 9999 1 1
93 120 538 410 1 248 100 11 45 14

Output 2

72490 231470

Constraints

For all test cases, $1\le A_i\le 10^9$.