Problem Y
Töskuröðun

Image from commons.wikimedia.org

As usual, Atli is travelling to yet another contest and has luggage with him. Rather than travelling light, he takes a near empty case with him so he can shop cheaply abroad. Often this results in him having to stand and wait for his luggage at the drop off when he is at his destination, so sometimes the people travelling with him who only have carry-on have to wait for him as well. In an effort to prevent this Atli intends to check in his luggage at the optimal time next time. When should he check in his luggage for it to arrive as soon as possible?

The bags first go from check-in to a large stack where they are stored until they go to the aircraft. The first bags end up at the bottom, so the first bag to arrive goes out last and the last bag to arrive goes out first. The bag order rearranges like this each time they are put in a stack.

Next they are put on carts, the first $K_ a$ bags are put in a stack on the first cart, the next $K_ a$ in a stack on the second cart and so on. If the number of bags is not a multiple of $K_ a$ there will simply be fewer bags on the last cart. The bag order rearranges like this each time they are put on carts, where the bags are then taken top to bottom from the first cart, then from the second and so on when they travel on.

Next the bags are put in a stack in the aircraft. If there are connecting flights the bags are put on carts with $K_ i$ bags each and then in a stack in the new aircraft at the $i$-th connection. Finally at the destination they are put on carts with $K_ b$ bags each, before they are then finally tossed onto the luggage drop off in their current order so the passengers can collect them.

Atli has researched all the airports beforehand, so he knows what the values $K_ a, K_ i, K_ b$ are for all the flights, along with the total number of bags $n$. If we number the check-ins from $1$ to $n$, number what should he be in the order to make sure his bag is dropped off first at the destination?

Input

The first line contains two integers $n$ and $m$, where $n$ is the number of bags and $m$ is the number of connecting flights. $n$ is always positive. The second line contains two integers $K_ a$ and $K_ b$, with $1 \leq K_ a, K_ b \leq 10^{18}$, the sizes of the carts at the departure and destination airports. Finally, if $m \neq 0$ there will be another line with $m$ integers $K_ i$, with $1 \leq K_ i \leq 10^{18}$, the sizes of the carts on each airport with a connecting flight, given in the order of travel.

Output

Print the number that corresponds to where Atli should be in the check-ins such that his bag is dropped off first at the destination.

Scoring

6 0
6 6

1

10 0
7 2

2

15 4
1 15
3 5 7 30

7