401380: GYM100425 I Road to Dragobat

Dragobat is the highest and the most elite ski-park of Ukraine. Apart from beautiful pine forest and breathtaking view, it is famous for its lacet roads.

The main road starts in the Yasinya-village (A) and ends in Dragobat (B). At the zero moment, two cars start to move from point A to point B and from point B to point A respectively. As soon as a car reaches its destination, it disappears from the road, and another car starts moving from the starting point. There are no other cars on the road. As a result, there are at most two cars on the track at any given moment of time.

The total length of the road is L. The road is split into one-lane and two-lane segments of given lengths H_i such that . The first and K-th segments are two-lane, and each pair of adjacent segments has a different number of lanes. Points A and B are located outside the road. Both one-lane and two-lane segments of the road are adjusted by the center of the road (see the image below).

A car is a square 1 × 1 which moves by the following rules:

• sides of the car are always parallel to the axes;
• the car which started from point A is always moving by the lower side of the road;
• the car which started from point B is always moving by the upper side of the road;
• the absolute value of X-speed of each car is equal to 0 or 1 at any given moment of time, the speed changes momentarily;
• you can ignore the time spent by cars to move among the Y axis (while changing from one-lane to two-lane and backwards).

If two car-squares intersect (have positive area of their intercestion), an accident is registered.

On the picture above, case 1 won't lead to an accident.

In case 2, an accident can happen if the upper car will start to move on to the one-lane part of the road before the lower car will pass the upper car.

In case 3, an accident will happen if none of the cars change their direction to the opposite.

Because of heavy snowfalls, cars can only see each other if the distance by the X-axis doesn't exceed R. A car can not be seen if it is still in point A or B.

When two drivers can see each other, they try to avoid any possible accident using the following rules:

1. Go on moving with initial speed if it won't lead to an accident.
2. If the current speeds of the cars will lead to an accident, then one of the cars should change its speed, while the second one should keep the initial speed. The driver which adjusts the speed is determined in such a way that the time of passage is minimal possible. If the time of passage is equal, the driver which started at point B changes its speed.

The time of passage is an interval of time between the moment when drivers first see each other and the moment when the car started in A will be to the right of the car started in B.

Calculate the number of cars which have successfully moved from A to B and from B to A at the moment T. A car arrives to the village only after it completely leaves the road.

The first line of input holds the time T (1 ≤ T ≤ 10⁹) and the visibility radius R (1 ≤ R ≤ 10⁶). The second line holds an odd number K (1 ≤ K ≤ 1000) which is the number of segments of the road. The third line holds K numbers H_i (2 ≤ H_i ≤ 1000) which are the lengths of the road segments. All numbers in the input are integers.

Output two integers: the number of cars which have successfully moved from A to B and the number of cars which have successfully moved from B to A at the moment T.

40 2
5
2 2 2 4 2

2 3

30 7
3
2 2 2

3 3

In the first example, cars will arrive at village B at moments 15 and 28, and at village A at moments 13, 26 and 39.

In the second example, cars will arrive at village B at moments 7, 15 and 23, and at village A at moments 11, 19 and 27.