시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 8 7 58.333%

문제

성관이는 소수 왕국에서 열리는 비밀 파티에 초대받았다. 파티에는 (성관이를 포함해) 총 n명의 사람들이 있었다. i번째 사람의 나이는 ai이다.

그들은 여러 개의 원형 테이블에 앉아 식사를 할 것이다. 사람들은 다음과 같은 조건으로 테이블에 앉아 식사를 하길 원한다.

  • 모든 사람이 정확히 하나의 테이블에 앉아 있어야 한다.
  • 하나의 테이블에는 적어도 3명의 사람이 앉아 있어야 한다.
  • 테이블에서 인접해 있는 모든 사람 쌍에 대해, 나이의 합이 소수여야 한다. 즉, 한 테이블에 x1, x2, …, xk번째 사람이 순서대로 앉아 있다면, ax1 + ax2, ax2 + ax3, …, axk + ax1가 모두 소수여야 한다.

위와 같은 조건을 만족하게 사람들을 앉히는 방법이 존재하는지 출력하시오.

입력

첫 번째 줄에 사람의 수를 나타내는 자연수 n이 주어진다. (1 ≤ n ≤ 200)

다음 줄에 각 사람의 나이를 나타내는 자연수 n개 (a1~an)가 주어진다. (2 ≤ ai ≤ 104)

출력

만약 조건을 만족하도록 사람들을 앉히는 것이 가능하다면, “Possible”을 출력한다.

그렇지 않다면, “Impossible”을 출력한다.

예제 입력 1

4
3 4 8 9

예제 출력 1

Possible

예제 입력 2

5
2 2 2 2 2

예제 출력 2

Impossible

예제 입력 3

12
2 3 4 5 6 7 8 9 10 11 12 13

예제 출력 3

Possible

예제 입력 4

24
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

예제 출력 4

Possible

힌트

첫 번째 예제에서는, 3-8-9-4의 순서로 테이블 하나에 모든 사람을 앉히면 된다.

두 번째 예제에서는, 2+2가 소수가 아니기 때문에, 불가능하다.

세 번째 예제에서는, 2-3-4-7-6-13-10-9-8-11-12-5의 순서로 모든 사람을 앉히면 된다.

네 번째 예제에서는, 다음과 같이 세 개의 테이블을 사용하면 된다.

  1. 2-3-4-7-6-5
  2. 8-9-10-13-16-15-14-17-12-11
  3. 18-19-24-23-20-21-22-25