Vegeta : "Kakarot trained in the hyperbolic time chamber just as we did! Now let’s see what he can do!"

Vegeta is determined to test Goku's abilities. He knows Goku has been training a lot to improve his fighting skills as well as his problem solving skills. So he decides to test both of these skills of Goku. Being a Super Saiyan himself, he is capable enough to test his fighting abilities. But he needs someone to test his problem solving skills. He asks his wife Bulma for help.



She gives Goku an array of n integers, and two more integers x and y. Goku is expected to find the largest multiple of y, which he can form by adding exactly x elements of the array. But the problem doesn't end here. He needs to do it for :
1. Taking any x elements of the array.
2. Taking any x odd-indexed elements of the array.
3. Taking any x even-indexed elements of the array.

Solve this problem for Goku and help him in proving himself as the number one Saiyan in this universe.

Input :

First line contains an integer n, the number of elements in the array.
Second line contains n space-separated integers, denoting the array.
Third line contains 2 integers, x and y, as described above.

Output :

Print 3 lines, each containing the answer to the question as described above, in the same order. If there is no possible answer for any of the 3 case, print -1 for that case.

Constraints :

1 ≤ n ≤ 1000
1 ≤ x ≤ n
1 ≤ y ≤ 10000
Sum of all elements of the array ≤ 10000