폰 발켄 백작의 울타리

사진 제공: Lascher

나이 든 폰 발켄 백작은 뒷마당 울타리를 따라 골똘히 생각하며 걷는다. 울타리는 같은 간격으로 땅에 박힌 기둥들이 반복되는 형태이다. 폰 발켄은 달리 할 일이 없어서 각 기둥 사이에서 자신이 몇 걸음을 걷는지 센다.

때로는 기둥 사이에서 두 걸음을 걷고 때로는 세 걸음을 걷기 때문에, 연속한 두 기둥 사이의 거리는 그의 보폭의 정수배가 아닌 것으로 드러난다.

[ht]

예제 케이스 2의 그림

Von Walken은 자신의 보폭이 항상 1미터라는 것을 알고 있으므로, 기둥 사이의 거리가 얼마일 수 있는지 생각하기 시작한다. ``가끔 기둥 사이에 3걸음을 넣을 수 있으니 그 거리는 반드시 2미터보다 길어야 하지만, 때로는 그 사이에 2걸음만 넣을 수 있으니 반드시 3미터보다 짧아야 한다.''

과제

걸음 수의 목록과 거리 $D$가 주어질 때, 두 기둥 사이의 거리가 $D$미터일 가능성이 있는지 판별한다. 기둥의 폭은 $0$인 것으로 간주할 수 있으며, 각 걸음은 엄격히 두 기둥 사이에 있다.

부동소수점 수로 인한 문제를 피하기 위해, 어떤 기둥을 최대 $10^{-7}$미터까지 옮기더라도 결과가 같음이 보장된다.

입력은 소수점 이하 최대 12자리인 실수 $D$과 정수 $N$이 들어 있는 한 줄, 그리고 공백으로 구분된 정수 걸음 수 목록 $c_1, c_2, \ldots, c_N$이 들어 있는 한 줄로 구성된다. $2 \leq c_i, D \leq 3$이고, $0 \leq N \leq 10\,000$이다.

$D$미터가 기둥 사이의 가능한 거리이면 프로그램은 possible`''을 출력하고, 그렇지 않으면 impossible`''을 출력해야 한다.