형형색색의 카멜레온

Christian은 소프트웨어 검증에 관한 정교한 연구를 하지 않을 때면 카멜레온을 기른다. 그의 카멜레온은 특별한 종으로, 서로 다른 n가지 색 중 하나만 띤다. 자연에 있는 카멜레온과 달리 Christian의 카멜레온은 아주 특정한 상황에서만 색을 바꾼다. Christian은 이른바 C4(Crazy Chameleon Colouring Concept)를 개발하는 데 꽤 오랜 시간이 걸렸고, 그 원리는 다음과 같다. 서로 다른 색을 가진 카멜레온 n - 1마리를 특수한 사육 테라리움에 넣고, 딸기 치즈와 간 소시지를 먹인 뒤, 밤새 어둠 속에 두면, 다음 날 아침 테라리움에는 y마리의 카멜레온이 있다. 놀라운 점은 y마리 중 어느 것도 처음의 n - 1가지 색을 띠지 않는다는 것이다. 대신 모두 처음에 테라리움에 없던 색을 띤다.

지난 주말 Christian은 친구에게 카멜레온을 빌려주어 크리스토퍼 스트리트 데이에 데려갔다. 물론 친구는 카멜레온이 최대한 화려해 보이기를 원했다. 그래서 Christian은 모든 색마다 카멜레온이 적어도 n - 1마리 있도록 C4 방법을 적용했다. 따라서 현재 Christian은 i번째 색의 카멜레온을 xi ≥ n - 1마리 보유하고 있다. 그런데 다가오는 휴일은 성 패트릭의 날이고, Christian은 이 특별한 날을 위해 모든 카멜레온이 같은 색을 띠면 멋질 것이라고 생각한다. 그는 C4 방법만 적용해서 그런 상태에 도달할 수 있는지 궁금해한다. 딸기 치즈가 부족하기 때문에, 모든 카멜레온이 같은 색을 띠게 하는 데 필요한 C4 적용 횟수의 최솟값을 알고 싶어 한다. 물론 그것이 가능하다면 말이다.

입력은 다음과 같다.

• 세 정수 n, c, y가 있는 한 줄:

  • n (2 ≤ n ≤ 105), 카멜레온이 띨 수 있는 서로 다른 색의 수.
  • c (1 ≤ c ≤ n), 마지막에 모든 카멜레온이 가져야 하는 색.
  • y (n - 1 ≤ y ≤ 109), C4 방법을 적용한 뒤 사육 테라리움에 있는 카멜레온의 수.

• n개의 정수 x1, . . . , xn이 있는 한 줄 (모든 i에 대해 n - 1 ≤ xi ≤ 109). xi는 Christian이 처음에 보유한 i번째 색 카멜레온의 수이다.

Christian의 카멜레온이 C4 방법만 적용해서 모두 c색을 띨 수 없다면 impossible을 출력한다. 그렇지 않으면 두 정수 a와 b를 출력한다. a는 모든 카멜레온이 c색을 띠게 하는 데 필요한 C4 적용 횟수의 최솟값이고, b는 마지막에 Christian이 보유한 카멜레온의 총수이다.

그림: Pixabay의 OpenClipart-Vectors.

그림 C.1: 첫 번째 예제의 그림. 처음에 Christian은 노란색 2마리, 초록색 3마리, 파란색 5마리를 보유한다. C4 방법을 5번 적용한 뒤에는 초록색 카멜레온 10마리가 된다. 벡터 (y, g, b)는 각 사육 단계에서 존재하는 노란색, 초록색, 파란색 카멜레온의 수를 나타낸다.