#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll rnd() {
  ll x = 0;
  for (int i = 0; i <= 17; ++i) x = 10 * x + rand() % 10;
  return x;
}
const int N = 1e5 + 100;
const int K = 9;
const int M = 2 * K * K;
const int S = 1 << (K + K);
int n, a[N], skad[M][S];
bool dp[M][S];
vector<int> factorize(int u) {
  vector<int> p;
  for (int i = 2; i * i <= u; ++i)
    if (u % i == 0) {
      p.push_back(i);
      while (u % i == 0) u /= i;
    }
  if (u > 1) p.push_back(u);
  return p;
}
int full(int x) { return (1 << x) - 1; }
int cnt[N], M1[N], M2[N], ans[N];
int qq(int q, vector<int> x) {
  int mask = 0;
  for (int i = 0; i <= (int)x.size() - 1; ++i)
    if (q % x[i] == 0) mask += 1 << i;
  return full((int)x.size()) - mask;
}
void solve(int x, int y) {
  if (x == y) return;
  auto fx = factorize(a[x]), fy = factorize(a[y]);
  int sz1 = (int)fx.size(), sz2 = (int)fy.size();
  for (int i = 0; i <= sz1 + sz2 - 1; ++i) cnt[i] = 0;
  vector<int> num;
  for (int i = 1; i <= n; ++i) {
    if (i == x || i == y) continue;
    M1[i] = qq(a[i], fx);
    M2[i] = qq(a[i], fy);
    bool flag = 0;
    for (int j = 0; j <= sz1 - 1; ++j)
      if (M1[i] >> j & 1 && cnt[j] < K + 2) flag = true;
    for (int j = 0; j <= sz2 - 1; ++j)
      if (M2[i] >> j & 1 && cnt[sz1 + j] < K + 2) flag = true;
    if (!flag) continue;
    num.push_back(i);
    for (int j = 0; j <= sz1 - 1; ++j)
      if (M1[i] >> j & 1) cnt[j]++;
    for (int j = 0; j <= sz2 - 1; ++j)
      if (M2[i] >> j & 1) cnt[sz1 + j]++;
  }
  sort(num.begin(), num.end());
  num.erase(unique(num.begin(), num.end()), num.end());
  int sz = (int)num.size();
  for (int i = 0; i <= sz; ++i)
    for (int j = 0; j <= S - 1; ++j) dp[i][j] = false;
  dp[0][0] = true;
  for (int i = 0; i <= sz - 1; ++i) {
    int x = num[i];
    for (int mask = 0; mask <= (1 << (sz1 + sz2)) - 1; ++mask) {
      if (!dp[i][mask]) continue;
      int nmask = mask | M1[x];
      dp[i + 1][nmask] = true;
      skad[i + 1][nmask] = mask;
      nmask = mask | (M2[x] << sz1);
      dp[i + 1][nmask] = true;
      skad[i + 1][nmask] = mask;
    }
  }
  if (!dp[sz][full(sz1 + sz2)]) return;
  ans[x] = 0;
  ans[y] = 1;
  int mask = full(sz1 + sz2);
  for (int i = sz - 1; 0 <= i; --i) {
    int nmask = skad[i + 1][mask], x = num[i];
    if (31 - __builtin_clz(nmask ^ mask) < sz1)
      ans[x] = 0;
    else
      ans[x] = 1;
    mask = nmask;
  }
  puts("YES");
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i] + 1);
  exit(0);
}
int main() {
  srand(2137);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  while (1.0 * clock() / CLOCKS_PER_SEC <= 0.4) {
    int x = rnd() % n + 1, y = rnd() % n + 1;
    solve(x, y);
  }
  puts("NO");
  return 0;
}
