#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <bitset> #include <array> using namespace std; #ifdef LOCAL #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);} #else #define eprintf(...) 42 #endif using ll = long long; using ld = long double; using uint = unsigned int; using ull = unsigned long long; template<typename T> using pair2 = pair<T, T>; using pii = pair<int, int>; using pli = pair<ll, int>; using pll = pair<ll, ll>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second clock_t startTime; double getCurrentTime() { return (double)(clock() - startTime) / CLOCKS_PER_SEC; } const int N = 2002; int SUCC = 0; int n; pii ord[N]; int d[N]; int dp[N][2 * N + 3]; int par[N][2 * N + 3]; char g[N][N]; void printTree() { int sum = 0; int X = 0; for (int i = 0; i < n; i++) { sum += d[i]; X ^= d[i]; ord[i] = mp(d[i], i); } assert(X == 0); assert(sum >= 2 * n - 2); assert(sum < 2 * n + 6); sort(ord, ord + n); reverse(ord, ord + n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) g[i][j] = '0'; g[i][n] = '\0'; } int p = 0; vector<int> a = vector<int>(); if (sum != 2 * n - 2) { sum = (sum - (2 * n - 2)) / 2; assert(ord[3].first >= 3); assert(ord[0].first >= 4); sum += 3; for (int i = 0; sum > 0 && i < 4; i++) for (int j = i + 1; sum > 0 && j < 4; j++) { int v = ord[i].second, u = ord[j].second; g[v][u] = g[u][v] = '1'; d[v]--; d[u]--; sum--; } p = 4; for (int i = 0; i < 4; i++) { int v = ord[i].second; for (int j = 0; j < d[v]; j++) a.push_back(v); } } else { p = 1; for (int i = 0; i < 1; i++) { int v = ord[i].second; for (int j = 0; j < d[v]; j++) a.push_back(v); } } for (int i = p; i < n; i++) { int v = ord[i].second; assert(!a.empty()); int u = a.back(); a.pop_back(); g[v][u] = g[u][v] = '1'; for (int j = 1; j < d[v]; j++) a.push_back(v); } printf("YES\n"); for (int i = 0; i < n; i++) { printf("%s\n", g[i]); } SUCC++; } void reduceFour() { int sum = 0, X = 0; for (int i = 0; i < n; i++) { sum += d[i]; X ^= d[i]; } assert(X == 0); assert(sum >= 2 * n - 2); assert(sum < 3 * n); while(sum >= 2 * n + 6) { int k = 30; for (int i = 0; i < n; i++) { if (d[i] < 8) continue; int x = (d[i] >> 2) << 2; while(x & ((1 << k) - 1)) k--; } if (k < 30) { int v = -1, u = -1; for (int i = 0; i < n; i++) { if (d[i] < 8) continue; if (((d[i] >> k) & 1) == 0) continue; if (v == -1) { v = i; } else if (u == -1) { u = i; } } assert(v != -1); if (u != -1) { sum -= 8; d[v] -= 4; d[u] -= 4; continue; } assert(k == 2); u = 0; while(u < n && (d[u] < 4 || d[u] >= 8)) u++; assert(u < n); int x = d[v] ^ d[u] ^ 3; assert(x < d[v]); assert((d[v] - x) + (d[u] - 3) <= 8); sum -= d[v] - x + d[u] - 3; d[v] = x; d[u] = 3; continue; } int v = -1, u = -1; for (int i = 0; i < n; i++) { if (d[i] < 4) continue; if ((d[i] & 2) == 0) continue; if (v == -1) { v = i; } else if (u == -1) { u = i; } } if (u != -1) { sum -= 4; d[v] -= 2; d[u] -= 2; continue; } v = -1; u = -1; for (int i = 0; i < n; i++) { if (d[i] < 4) continue; if ((d[i] & 1) == 0) continue; if (v == -1) { v = i; } else if (u == -1) { u = i; } } if (u != -1) { sum -= 2; d[v] -= 1; d[u] -= 1; continue; } for (int i = 0; i < n; i++) ord[i] = mp(d[i], i); sort(ord, ord + n); reverse(ord, ord + n); int p = 0; while(p < n && ord[p].first >= 4) p++; assert(p % 2 == 0); while(sum >= 2 * n + 6 && p > 0) { p -= 2; int v = ord[p].second, u = ord[p + 1].second; int x = d[v] ^ d[u]; sum -= d[v] + d[u]; if (x == 3) { d[v] = 2; d[u] = 1; } else { d[v] = 3; d[u] = 3 ^ x; } sum += d[v] + d[u]; } return; } } bool checkThree(int a, int b, int c, int ones, int twos) { int sum = a + b + c + ones * 1 + twos * 2; if (sum < 2 * n - 2) return false; assert(sum % 2 == 0); if (a < b) swap(a, b); if (b < c) swap(b, c); if (a < b) swap(a, b); assert(a > 1); if (b == 1) { return true; } if (c == 1) { if (twos > 0) { c = 2; ones++; twos--; } } if (c == 1) { return sum == 2 * n - 2; } return (sum - (2 * n - 2)) / 2 <= 1 + twos; } void printThree() { /* eprintf("print 3\n"); for (int i = 0; i < n; i++) eprintf("%d ", d[i]); eprintf("\n"); */ int sum = 0; int X = 0; for (int i = 0; i < n; i++) { sum += d[i]; X ^= d[i]; ord[i] = mp(d[i], i); } assert(X == 0); assert(sum >= 2 * n - 2); sort(ord, ord + n); reverse(ord, ord + n); assert(ord[3].first <= 2); if (ord[0].first == 2) { if (sum == 2 * n) { d[ord[0].second] = d[ord[1].second] = 1; sum -= 2; } } if (sum == 2 * n - 2) { printTree(); return; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) g[i][j] = '0'; g[i][n] = '\0'; } int A = ord[0].second, B = ord[1].second, C = ord[2].second; sum = (sum - (2 * n - 2)) / 2; assert(sum > 0); assert(d[C] >= 2); g[A][B] = g[B][A] = g[A][C] = g[C][A] = g[B][C] = g[C][B] = '1'; d[A] -= 2; d[B] -= 2; d[C] -= 2; sum--; int p = 3; while(sum > 1) { assert(p < n); int v = ord[p++].second; assert(d[v] == 2); if (d[A] < d[B]) swap(A, B); if (d[B] < d[C]) swap(B, C); if (d[A] < d[B]) swap(A, B); assert(d[A] + d[B] >= 2); if (d[B] == 0) { assert(p < n); int u = ord[p++].second; assert(d[u] == 2); g[A][v] = g[v][A] = g[A][u] = g[u][A] = g[v][u] = g[u][v] = '1'; d[A] -= 2; d[v] -= 2; d[u] -= 2; sum--; } else { g[A][v] = g[B][v] = g[v][A] = g[v][B] = '1'; sum--; d[A]--; d[B]--; d[v] -= 2; } } if (d[A] < d[B]) swap(A, B); if (d[B] < d[C]) swap(B, C); if (d[A] < d[B]) swap(A, B); if (p < n && ord[p].first == 2) { int v = ord[p].second; d[A]--; g[A][v] = g[v][A] = '1'; p++; while(p < n && ord[p].first == 2) { int u = ord[p++].second; g[v][u] = g[u][v] = '1'; v = u; } if (sum == 0) { assert(p < n); int u = ord[p++].second; g[v][u] = g[u][v] = '1'; } else { if (d[B] > 0) { d[B]--; g[B][v] = g[v][B] = '1'; } else { assert(d[A] > 0); d[A]--; g[A][v] = g[v][A] = '1'; } } } while(p < n) { int v = ord[p].second; assert(d[v] == 1); if (d[B] > 0) swap(A, B); if (d[C] > 0) swap(A, C); assert(d[A] > 0); d[A]--; g[A][v] = g[v][A] = '1'; p++; } printf("YES\n"); for (int i = 0; i < n; i++) { printf("%s\n", g[i]); } SUCC++; } void solve() { //eprintf("SOLVE\n"); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &ord[i].first); ord[i].second = i; } if (n == 2) { printf("YES\n01\n10\n"); SUCC++; return; } if (n == 3) { printf("NO\n"); return; } sort(ord, ord + n); reverse(ord, ord + n); int ones = 0; while(ones < n - 3 && ord[n - 1 - ones].first == 1) ones++; int twos = n - 3 - ones; for (int x = 0; x <= 1 && x <= twos; x++) { int nones = ones + x, ntwos = twos - x; int X = (nones & 1) ^ ((ntwos & 1) << 1); for (int c = 1; c <= ord[2].first; c++) for (int b = 1; b <= ord[1].first; b++) { int a = b ^ c ^ X; if (a == 0 || a > ord[0].first) continue; if (!checkThree(a, b, c, nones, ntwos)) continue; d[ord[0].second] = a; d[ord[1].second] = b; d[ord[2].second] = c; for (int i = 3; i < n - nones; i++) d[ord[i].second] = 2; for (int i = n - nones; i < n; i++) d[ord[i].second] = 1; printThree(); return; } } if (ord[3].first <= 2) { printf("NO\n"); return; } int sum = 0; for (int i = 0; i < n; i++) sum += ord[i].first; if (sum >= 3 * n) { for (int i = 0; i + 1 < n; i += 2) ord[i].first = ord[i + 1].first; if (n & 1) { ord[n - 1].first = 1; if (ord[0].first % 2 == 0) { ord[0].first--; ord[1].first--; } ord[0].first--; } sum = 0; for (int i = 0; i < n; i++) sum += ord[i].first; assert(sum >= 2 * n - 2); assert(sum % 2 == 0); for (int i = 0; i + 1 < n; i += 2) { int x = (ord[i].first - 1); x = min(x, (sum - (2 * n - 2)) / 2); if ((n & 1) && i == 0) x -= x & 1; sum -= 2 * x; ord[i].first -= x; ord[i + 1].first -= x; } assert(sum == 2 * n - 2); for (int i = 0; i < n; i++) d[ord[i].second] = ord[i].first; printTree(); } else { for (int i = 0; i <= n; i++) for (int x = 0; x < 2 * ord[0].first; x++) dp[i][x] = -1; dp[n][0] = 0; for (int i = n - 1; i >= 0; i--) for (int x = 0; x < 2 * ord[i].first; x++) { if (dp[i + 1][x] == -1) continue; for (int y = (i <= 3 ? 3 : 1); y <= ord[i].first; y++) { int z = x ^ y; int w = dp[i + 1][x] + y; if (w <= dp[i][z]) continue; dp[i][z] = w; par[i][z] = y; } } if (dp[0][0] < 2 * n - 2) { printf("NO\n"); return; } int z = 0; for (int p = 0; p < n; p++) { int x = par[p][z]; d[ord[p].second] = x; z ^= x; } reduceFour(); bool all3 = true; int sum = 0; for (int i = 0; i < n; i++) { all3 &= d[i] <= 3; sum += d[i]; } assert(sum >= 2 * n - 2); if (all3) { sum = (sum - (2 * n - 2)) / 2; int L3 = -1, L2 = -1; for (int i = 0; sum > 0 && i < n; i++) { if (d[i] == 1) continue; if (d[i] == 2) { if (L2 == -1) { L2 = i; } else { d[i]--; d[L2]--; sum--; L2 = -1; } } else if (d[i] == 3) { if (L3 == -1) { L3 = i; } else { d[i]--; d[L3]--; sum--; if (sum == 0) break; d[i]--; d[L3]--; sum--; L3 = -1; } } else assert(false); } assert(sum == 0); } else { assert(sum < 2 * n + 6); } printTree(); } } int main() { startTime = clock(); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int t; scanf("%d", &t); while(t--) { solve(); } fprintf(stderr, "YES = %d\n", SUCC); return 0; }