The most frightening word in nuclear physics is “Oops!..”
The Beloyarsk Nuclear Power Plant has been severely damaged in the recent earthquake of magnitude 7
that has stricken the Ural mountains. The nuclear reactor is intact, but almost all control systems are not functioning.
In particular, the sensors are out of order and the staff can only guess what is happening inside the reactor.
The reactor must be stopped as soon as possible! For this, the staff has to know the current positions of the control rods.
Control rods are used for controlling the nuclear reaction. Their steel shells are filled with boron, which is capable of
absorbing a large number of neutrons. When the rods are inserted into the reactor core, they absorb neutrons and
the reaction slows down. Conversely, when the rods are removed from the core, the number of neutrons increases and the reaction
accelerates. At the BNPP, the rods can be shifted from the zero position, when they are removed completely,
to the depth of n mm, which is the complete insertion. Inserting the rods without knowing the state of the reactor
may be dangerous. For example, when control rods were inserted into the reactor core at the Chernobyl Nuclear Power Plant in 1986,
the reactor went out of control. That is why it is important to determine the current positions of the rods
before taking any further actions.
The staff have a log with all the changes in the positions of the rods. Unfortunately,
the log contains only the numbers of millimeters by which the rods were shifted, but it does not say
in which direction—up or down. Now the staff need your help.
The first line contains integers n, s, and k, which are the maximum insertion depth of the rods,
the initial insertion depth, and the number of entries in the log, respectively (0 ≤ s ≤ n ≤ 109;
n > 0; 1 ≤ k ≤ 40). In the second line you are given k positive integers, which are the values of
the shifts of the rods in chronological order. It is guaranteed that there exists a sequence of shifts consistent
with the log such that during this sequence of shifts the rods are always inserted at least 0 mm and at most
n mm deep.
Output the minimum and maximum possible insertion depths of the rods after all the shifts.
10 3 3
4 5 1
Problem Author: Alexander Klepinin (prepared by Daniil Ayzenshteyn)
Problem Source: Open Ural FU Championship 2011