#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
using namespace std;
vector<vector<int>> kek(3);
vector<int> ans;

int nod(int a, int b) {
	while (b != 0) {
		int buf = b;
		b = a % b;
		a = buf;
	}
	return a;
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		if (num == 1) {
			cout << "Impossible";
			return 0;
		}
		for (int j = 0; j < 3; j++) {
			if (kek[j].size() == 0) {
				kek[j].push_back(num);
				ans.push_back(j + 1);
				break;
			}
			auto k = nod(kek[j][0], num);
			if (k != 1) {
				kek[j][0] = k;
				ans.push_back(j + 1);
				break;
			}
		}
		if (ans.size() != i + 1) {
			cout << "Impossible";
			return 0;
		}
	}
	cout << "Possible\n";
	for (auto i : ans) {
		cout << i << " ";
	}

	//system("pause");
	return 0;
}