Colourful Chameleons

When Christian is not doing sophisticated research in software validation, he breeds chameleons. His chameleons belong to a special species and each one takes on exactly one of n distinct colours. Unlike their counterparts in nature, Christian's chameleons change colour only under very specific circumstances. It took Christian quite a long time to develop his so-called Crazy Chameleon Colouring Concept (C4), which works as follows. If he puts n - 1 chameleons with distinct colours into a special breeding terrarium, feeds them strawberry cheese and liver sausage, and lets them stay in the dark overnight, then there will be y chameleons in the terrarium the next morning. The crazy thing is that none of the y chameleons has any of the n - 1 original colours. Instead, all of them take on the colour that was not present in the breeding terrarium initially.

Last weekend Christian lent his chameleons to a friend for Christopher Street Day. Of course his friend wanted the chameleons to look as colourful as possible. That is why Christian applied the C4 method in such a way that there were at least n - 1 chameleons available of every single colour. Therefore, Christian currently has xi ≥ n - 1 chameleons of the ith colour. However, the next holiday coming up is St. Patrick's Day, and Christian thinks it would be super cool if all his chameleons took on the same colour for this special event. He wonders whether such a state can be reached by applying the C4 method exclusively. Because he is running low on strawberry cheese, he would like to know the minimal number of C4 applications needed for all his chameleons to take on the same colour, provided that this is even possible.

The input consists of:

• A line with three integers n, c, and y:

  • n (2 ≤ n ≤ 105), the number of different colours the chameleons can take on.
  • c (1 ≤ c ≤ n), the colour that all chameleons should have in the end.
  • y (n - 1 ≤ y ≤ 109), the number of chameleons in the breeding terrarium after applying the C4 method.

• A line with n integers x1, . . . , xn (n - 1 ≤ xi ≤ 109 for all i), where xi is the number of chameleons of the ith colour that Christian possesses initially.

If it is impossible for Christian's chameleons to all take on colour c by applying the C4 method exclusively, output impossible. Otherwise output two integers a and b, where a is the minimal number of C4 applications necessary for all chameleons to have colour c, and b is the total number of chameleons that Christian possesses in the end.

Image by OpenClipart-Vectors on Pixabay.

Figure C.1: Illustration of the first sample case. Initially, Christian owns 2 yellow, 3 green, and 5 blue chameleons. After 5 applications of the C4 method he has 10 green chameleons. The vectors (y, g, b) denote the number of yellow, green, and blue chameleons available in the respective breeding step.