Problem: Let's consider an n × n square matrix, consisting of digits one and zero.

We'll consider a matrix good, if it meets the following condition: in each row of the matrix all ones go in one group. That is, each row of the matrix looks like that 00...0011...1100...00 (or simply consists of zeroes if it has no ones).

You are given matrix a of size n × n, consisting of zeroes and ones. Your task is to determine whether you can get a good matrix b from it by rearranging the columns or not.

Input

The first line contains integer n (1 ≤ n ≤ 500) — the size of matrix a.

Each of n following lines contains n characters "0" and "1" — matrix a. Note that the characters are written without separators.

Output

Print "YES" in the first line, if you can rearrange the matrix columns so as to get a good matrix b. In the next n lines print the good matrix b. If there are multiple answers, you are allowed to print any of them.

If it is impossible to get a good matrix, print "NO".

Examples

Input

6
100010
110110
011001
010010
000100
011001


Output

YES
011000
111100
000111
001100
100000
000111


Input

3
110
101
011


Output

NO

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int INVALID = -1;
const int UNMARKED = 0;
const int MARKED = 1;
const int PENDING = 2;
const int QUEUED = 3;
const int FULL = 4;
const int PARTIAL = 5;
const int TOP = 6;
const int LEAFNODE = 0;
const int PNODE = 1;
const int QNODE = 2;
struct PQTreeNode {
  int kind;
  int parent;
  int extremechilds[2];
  int siblings[2];
  int othersibling(int x) {
    for (int k = (0); k < (2); ++k)
      if (siblings[k] == x) return siblings[1 - k];
    assert(false);
    return -1;
  }
  void replaceextremechild(int a, int b) {
    for (int k = (0); k < (2); ++k)
      if (extremechilds[k] == a) {
        extremechilds[k] = b;
        return;
      }
    assert(false);
  }
  void replacesibling(int a, int b) {
    for (int k = (0); k < (2); ++k)
      if (siblings[k] == a) {
        siblings[k] = b;
        return;
      }
    assert(false);
  }
  bool isextreme() { return siblings[0] == -1 || siblings[1] == -1; }
  void init(int _kind) {
    kind = _kind;
    parent = -1;
    extremechilds[0] = extremechilds[1] = siblings[0] = siblings[1] = -1;
    state = UNMARKED, nmarkedchilds = 0, nblackdescendants = 0,
    fullhead = fullnxt = -1, fullcnt = 0, partialhead = partialnxt = -1,
    partialcnt = 0;
  }
  int state, nmarkedchilds, nblackdescendants;
  int fullhead, fullnxt, fullcnt;
  int partialhead, partialnxt, partialcnt;
};
struct PQTree {
  bool failed;
  vector<PQTreeNode> nodes;
  queue<int> pool;
  vector<int> markednodes;
  queue<int> q;
  int virtualtop;
  int createnode(int kind) {
    int ret;
    if (!pool.empty()) {
      ret = pool.front();
      pool.pop();
    } else {
      ret = ((int)(nodes).size());
      nodes.push_back(PQTreeNode());
    }
    nodes[ret].init(kind);
    return ret;
  }
  void releasenode(int at) {
    nodes[at].kind = INVALID;
    pool.push(at);
  }
  void fixparent(int at) {
    int par = nodes[at].parent;
    if (par != -1 && nodes[par].kind == QNODE && !nodes[at].isextreme())
      nodes[at].parent = -1;
  }
  void removenode(int at) {
    if (at == -1) return;
    int par = nodes[at].parent;
    for (int k = (0); k < (2); ++k) {
      int to = nodes[at].siblings[k], oth = nodes[at].siblings[1 - k];
      if (to == -1)
        nodes[par].replaceextremechild(at, oth);
      else
        nodes[to].replacesibling(at, oth);
    }
    nodes[at].parent = nodes[at].siblings[0] = nodes[at].siblings[1] = -1;
  }
  void appendnode(int at, int par) {
    if (at == -1) return;
    int prv = nodes[par].extremechilds[1];
    nodes[at].parent = par, nodes[at].siblings[0] = prv,
    nodes[at].siblings[1] = -1;
    if (prv == -1)
      nodes[par].extremechilds[0] = at;
    else {
      nodes[prv].replacesibling(-1, at);
      fixparent(prv);
    }
    nodes[par].extremechilds[1] = at;
  }
  void appendall(int at, int par) {
    if (at == -1) return;
    int prv = nodes[par].extremechilds[1], fst = nodes[at].extremechilds[0],
        lst = nodes[at].extremechilds[1];
    nodes[fst].parent = par, nodes[fst].replacesibling(-1, prv),
    nodes[lst].parent = par;
    if (prv == -1)
      nodes[par].extremechilds[0] = fst;
    else {
      nodes[prv].replacesibling(-1, fst);
      fixparent(prv), fixparent(fst);
    }
    nodes[par].extremechilds[1] = lst;
    releasenode(at);
  }
  void replacenode(int at, int by) {
    int par = nodes[at].parent, prv = nodes[at].siblings[0],
        nxt = nodes[at].siblings[1];
    nodes[by].parent = par, nodes[by].siblings[0] = prv,
    nodes[by].siblings[1] = nxt;
    if (prv == -1) {
      if (par != -1) nodes[par].replaceextremechild(at, by);
    } else
      nodes[prv].replacesibling(at, by);
    if (nxt == -1) {
      if (par != -1) nodes[par].replaceextremechild(at, by);
    } else
      nodes[nxt].replacesibling(at, by);
    nodes[at].parent = nodes[at].siblings[0] = nodes[at].siblings[1] = -1;
  }
  void expandnode(int at) {
    int par = nodes[at].parent, prv = nodes[at].siblings[0],
        nxt = nodes[at].siblings[1], fst = nodes[at].extremechilds[0],
        lst = nodes[at].extremechilds[1];
    nodes[fst].parent = nodes[lst].parent = par,
    nodes[fst].replacesibling(-1, prv), nodes[lst].replacesibling(-1, nxt);
    if (prv == -1)
      nodes[par].replaceextremechild(at, fst);
    else {
      nodes[prv].replacesibling(at, fst);
      fixparent(fst);
    }
    if (nxt == -1)
      nodes[par].replaceextremechild(at, lst);
    else {
      nodes[nxt].replacesibling(at, lst);
      fixparent(lst);
    }
    releasenode(at);
  }
  void reducenode(int &at) {
    if (nodes[at].extremechilds[0] == -1 && nodes[at].extremechilds[1] == -1) {
      releasenode(at);
      at = -1;
      return;
    }
    if (nodes[at].extremechilds[0] == nodes[at].extremechilds[1]) {
      int old = at;
      at = nodes[at].extremechilds[0];
      nodes[at].parent = -1;
      releasenode(old);
      return;
    }
  }
  void reversenode(int at) {
    if (at == -1) return;
    swap(nodes[at].extremechilds[0], nodes[at].extremechilds[1]);
  }
  void setmarked(int at) {
    int par = nodes[at].parent;
    nodes[at].state = MARKED;
    if (par != -1) ++nodes[par].nmarkedchilds;
  }
  bool mark(const vector<int> &ids) {
    for (int i = (0); i < (((int)(ids).size())); ++i) {
      int at = ids[i];
      assert(nodes[at].state == UNMARKED);
      nodes[at].state = QUEUED;
      markednodes.push_back(at), q.push(at);
    }
    int npendingblocks = 0;
    bool markedroot = false;
    while (((int)(q).size()) + npendingblocks + (markedroot ? 1 : 0) > 1) {
      if (q.empty()) return false;
      int at = q.front(), par = nodes[at].parent;
      q.pop();
      assert(nodes[at].state == QUEUED);
      if (par == -1 && nodes[at].siblings[0] == -1 &&
          nodes[at].siblings[1] == -1) {
        setmarked(at);
        assert(!markedroot);
        markedroot = true;
        continue;
      }
      if (par == -1)
        for (int k = (0); k < (2); ++k) {
          int to = nodes[at].siblings[k];
          assert(to != -1);
          if (nodes[to].state == MARKED) {
            par = nodes[at].parent = nodes[to].parent;
            break;
          }
        }
      if (par != -1) {
        setmarked(at);
        if (nodes[par].state == UNMARKED) {
          nodes[par].state = QUEUED;
          markednodes.push_back(par), q.push(par);
        }
        for (int k = (0); k < (2); ++k) {
          int prv = at, to = nodes[at].siblings[k];
          if (to == -1 || nodes[to].state != PENDING) continue;
          --npendingblocks;
          while (to != -1 && nodes[to].state == PENDING) {
            nodes[to].parent = par;
            setmarked(to);
            tie(prv, to) = make_pair(to, nodes[to].othersibling(prv));
          }
        }
      } else {
        nodes[at].state = PENDING;
        ++npendingblocks;
        for (int k = (0); k < (2); ++k) {
          int to = nodes[at].siblings[k];
          assert(to != -1);
          if (nodes[to].state != PENDING) continue;
          --npendingblocks;
        }
      }
    }
    while (!q.empty()) {
      int at = q.front();
      q.pop();
      nodes[at].state = MARKED;
    }
    if (npendingblocks == 1) {
      int l = -1, r = -1, cnt = 0;
      for (int i = (0); i < (((int)(markednodes).size())); ++i) {
        int at = markednodes[i];
        if (nodes[at].state != PENDING) continue;
        ++cnt;
        if (l == -1 && r == -1) l = r = at;
      }
      assert(l != -1 && r != -1);
      if (cnt >= 2) {
        virtualtop = createnode(QNODE);
        markednodes.push_back(virtualtop);
        nodes[virtualtop].state = MARKED;
        nodes[l].parent = virtualtop, setmarked(l);
        {
          int nl = nodes[l].siblings[0];
          while (nl != -1 && nodes[nl].state != UNMARKED)
            tie(nl, l) = make_pair(nodes[nl].othersibling(l), nl),
                    nodes[l].parent = virtualtop, setmarked(l);
        }
        {
          int nr = nodes[r].siblings[1];
          while (nr != -1 && nodes[nr].state != UNMARKED)
            tie(nr, r) = make_pair(nodes[nr].othersibling(r), nr),
                    nodes[r].parent = virtualtop, setmarked(r);
        }
        nodes[l].parent = nodes[r].parent = virtualtop;
        nodes[virtualtop].extremechilds[0] = l,
        nodes[virtualtop].extremechilds[1] = r;
      }
    }
    return true;
  }
  bool reduce(const vector<int> &ids) {
    for (int i = (0); i < (((int)(ids).size())); ++i) {
      int at = ids[i];
      ++nodes[at].nblackdescendants;
      q.push(at);
    }
    while (!q.empty()) {
      int at = q.front(), par = nodes[at].parent,
          curblackdescendants = nodes[at].nblackdescendants;
      q.pop();
      bool islast = curblackdescendants == ((int)(ids).size());
      if (nodes[at].partialcnt >= 3 || !islast && nodes[at].partialcnt >= 2)
        return false;
      bool allfull = at != virtualtop;
      if (allfull)
        for (int x = nodes[at].extremechilds[0], y = -1; x != -1;
             tie(x, y) = make_pair(nodes[x].othersibling(y), x))
          if (nodes[x].state != FULL) {
            allfull = false;
            break;
          }
      if (nodes[at].kind == LEAFNODE || allfull) {
        nodes[at].state = islast ? TOP : FULL;
        for (int x = nodes[at].fullhead; x != -1; x = nodes[x].fullnxt)
          fixparent(x);
      } else if (nodes[at].kind == PNODE) {
        int partial1 = nodes[at].partialhead,
            partial2 = partial1 != -1 ? nodes[partial1].partialnxt : -1;
        removenode(partial1);
        removenode(partial2);
        reversenode(partial2);
        int full = createnode(PNODE);
        markednodes.push_back(full);
        for (int x = nodes[at].fullhead; x != -1; x = nodes[x].fullnxt) {
          removenode(x);
          appendnode(x, full);
        }
        reducenode(full);
        int empty = at;
        at = createnode(QNODE);
        markednodes.push_back(at);
        replacenode(empty, at);
        if (!islast) {
          reducenode(empty);
          appendnode(empty, at);
          appendall(partial1, at);
          appendnode(full, at);
          nodes[at].state = PARTIAL;
        } else {
          appendall(partial1, at);
          appendnode(full, at);
          appendall(partial2, at);
          if (nodes[empty].extremechilds[0] == -1 &&
              nodes[empty].extremechilds[1] == -1)
            reducenode(empty);
          else {
            replacenode(at, empty);
            reducenode(at);
            appendnode(at, empty);
          }
          nodes[at].state = TOP;
        }
      } else if (nodes[at].kind == QNODE) {
        int tmp = nodes[at].fullcnt >= 1      ? nodes[at].fullhead
                  : nodes[at].partialcnt >= 1 ? nodes[at].partialhead
                                              : -1,
            l = tmp, r = tmp;
        {
          int nl = nodes[l].siblings[0];
          while (nl != -1 && nodes[nl].state != UNMARKED)
            tie(nl, l) = make_pair(nodes[nl].othersibling(l), nl);
          if (nodes[l].siblings[0] != nl) reversenode(l);
        }
        {
          int nr = nodes[r].siblings[1];
          while (nr != -1 && nodes[nr].state != UNMARKED)
            tie(nr, r) = make_pair(nodes[nr].othersibling(r), nr);
          if (nodes[r].siblings[1] != nr) reversenode(r);
        }
        if (at != virtualtop &&
            nodes[nodes[at].extremechilds[0]].state == FULL &&
            nodes[nodes[at].extremechilds[1]].state == FULL)
          return false;
        for (int x = nodes[at].fullhead; x != -1; x = nodes[x].fullnxt)
          if (x != l && x != r) fixparent(x);
        int partial1 = nodes[at].partialhead,
            partial2 = partial1 != -1 ? nodes[partial1].partialnxt : -1;
        if (partial1 != -1 && partial1 != l && partial1 != r ||
            partial2 != -1 && partial2 != l && partial2 != r)
          return false;
        if (!islast) {
          if (nodes[l].isextreme() && nodes[l].state != PARTIAL) {
            swap(l, r);
            if (nodes[l].state == PARTIAL) reversenode(l);
          }
          if (!nodes[r].isextreme() || l != r && nodes[r].state == PARTIAL)
            return false;
          if (r != nodes[at].extremechilds[1]) reversenode(at);
          if (nodes[l].state == PARTIAL)
            expandnode(l);
          else
            fixparent(l);
          nodes[at].state = PARTIAL;
        } else {
          if (nodes[l].state == PARTIAL)
            expandnode(l);
          else
            fixparent(l);
          if (nodes[r].state == PARTIAL)
            reversenode(r), expandnode(r);
          else
            fixparent(r);
          nodes[at].state = TOP;
        }
      } else
        assert(false);
      if (par != -1 && !islast) {
        if (nodes[at].state == FULL) {
          nodes[at].fullnxt = nodes[par].fullhead;
          nodes[par].fullhead = at;
          ++nodes[par].fullcnt;
        }
        if (nodes[at].state == PARTIAL) {
          nodes[at].partialnxt = nodes[par].partialhead;
          nodes[par].partialhead = at;
          ++nodes[par].partialcnt;
        }
        nodes[par].nblackdescendants += curblackdescendants;
        --nodes[par].nmarkedchilds;
        if (nodes[par].nmarkedchilds == 0) q.push(par);
      }
    }
    if (virtualtop != -1) {
      for (int x = nodes[virtualtop].fullhead; x != -1; x = nodes[x].fullnxt)
        fixparent(x);
      for (int x = nodes[virtualtop].partialhead; x != -1;
           x = nodes[x].partialnxt)
        fixparent(x);
    }
    return true;
  }
  void cleanup() {
    for (int i = (0); i < (((int)(markednodes).size())); ++i) {
      int at = markednodes[i];
      nodes[at].state = UNMARKED;
      nodes[at].nmarkedchilds = 0;
      nodes[at].nblackdescendants = 0;
      nodes[at].fullhead = -1, nodes[at].fullnxt = -1, nodes[at].fullcnt = 0,
      nodes[at].partialhead = -1, nodes[at].partialnxt = -1,
      nodes[at].partialcnt = 0;
    }
    if (virtualtop != -1) {
      releasenode(virtualtop);
      virtualtop = -1;
    }
    markednodes.clear();
    q = queue<int>();
  }
  void print(int at) {
    if (nodes[at].kind == PNODE)
      printf("{");
    else if (nodes[at].kind == QNODE)
      printf("[");
    else if (nodes[at].kind == LEAFNODE)
      printf("%c", 'A' + at);
    else
      printf("?");
    for (int x = nodes[at].extremechilds[0], y = -1; x != -1;
         tie(x, y) = make_pair(nodes[x].othersibling(y), x)) {
      if (y != -1) printf(",");
      print(x);
    }
    if (nodes[at].kind == PNODE)
      printf("}");
    else if (nodes[at].kind == QNODE)
      printf("]");
  }
  void print() {
    for (int at = (0); at < (((int)(nodes).size())); ++at)
      if (nodes[at].kind != INVALID && nodes[at].parent == -1 &&
          nodes[at].siblings[0] == -1 && nodes[at].siblings[1] == -1 &&
          at != virtualtop) {
        print(at);
        puts("");
      }
  }
  void init(int n) {
    failed = false;
    pool = queue<int>();
    nodes.clear();
    for (int i = (0); i < (n); ++i) createnode(LEAFNODE);
    int root = createnode(PNODE);
    for (int i = (0); i < (n); ++i) appendnode(i, root);
    markednodes.clear();
    q = queue<int>();
    virtualtop = -1;
  }
  bool update(const vector<int> &ids) {
    if (failed) return false;
    if (!mark(ids)) {
      failed = true;
      return false;
    }
    if (!reduce(ids)) {
      failed = true;
      return false;
    }
    cleanup();
    return true;
  }
  void buildfrontier(vector<int> &frontier, int at) {
    if (nodes[at].kind == LEAFNODE)
      frontier.push_back(at);
    else
      for (int x = nodes[at].extremechilds[0], y = -1; x != -1;
           tie(x, y) = make_pair(nodes[x].othersibling(y), x))
        buildfrontier(frontier, x);
  }
  vector<int> frontier() {
    for (int at = (0); at < (((int)(nodes).size())); ++at)
      if (nodes[at].kind != INVALID && nodes[at].parent == -1 &&
          nodes[at].siblings[0] == -1 && nodes[at].siblings[1] == -1 &&
          at != virtualtop) {
        vector<int> ret;
        buildfrontier(ret, at);
        return ret;
      }
    assert(false);
    return vector<int>();
  }
};
const int MAXN = 500;
int n;
char g[MAXN][MAXN + 1];
PQTree tree;
vector<int> ord;
bool solve() {
  tree.init(n);
  for (int x = (0); x < (n); ++x) {
    vector<int> cur;
    for (int y = (0); y < (n); ++y)
      if (g[x][y] == '1') cur.push_back(y);
    if (!tree.update(cur)) return false;
  }
  ord = tree.frontier();
  assert(((int)(ord).size()) == n);
  return true;
}
void run() {
  scanf("%d", &n);
  for (int x = (0); x < (n); ++x) scanf("%s", g[x]);
  if (!solve()) {
    printf("NO\n");
    return;
  }
  printf("YES\n");
  for (int x = (0); x < (n); ++x) {
    for (int y = (0); y < (n); ++y) printf("%c", g[x][ord[y]]);
    puts("");
  }
}
int main() {
  run();
  return 0;
}