#include<bits/stdc++.h>
using namespace std;

const int INF = (1<<21);
const int MAX_V = 200;

const int S=52;

struct state{
  vector<int> v;
  state(vector<int> v): v(v) {}
  state( char c ){
    v = vector<int>(S);
    if( c <= 'Z' ) v[c-'A']=-1;
    else v[26+c-'a']=-1;
  }
  state(int x){
    v=vector<int>(S,x);
  }
  state(){}
  state operator+(const state& x) const{
    vector<int> res(v.size());
    for(int i=0;i<(int)res.size();i++)
      res[i] = v[i]+x.v[i];
    return state(res);
  }
  state operator-(const state& x){
    vector<int> res(v.size());
    for(int i=0;i<(int)res.size();i++)
      res[i] = v[i]-x.v[i];
    return state(res);
  }
  state operator*(int x){
    vector<int> res=v;
    for(int i=0;i<(int)res.size();i++) res[i]*=x;
    return res;
  }
  bool operator<(const state& x) const{
    for(int i=0;i<(int)v.size();i++){
      if( v[i] == x.v[i] ) continue;
      return v[i] < x.v[i];
    }
    return false;
  }
  bool operator==(const state& x) const{
    for(int i=0;i<x.v.size();i++)
      if( v[i] != x.v[i] ) return false;
    return true;
  }
  void view(){
    for(int i=0;i<v.size();i++){
      cout << v[i] << " ";
    }
    cout << endl;
  }
};

struct edge{
  int to, cap,rev;
  state cost;
  edge( int to, int cap, state cost, int rev) : to(to),cap(cap),cost(cost),rev(rev) {}
  edge(){}
};


typedef pair<state,int> P;

int V;
vector<edge> G[MAX_V];
state h[MAX_V];
state dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
 
void init(){
  for(int i = 0 ; i < MAX_V ; i++){
    G[i].clear();
  }
}
 
void add_edge(int from,int to,int cap,state cost){
  G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
  G[to].push_back((edge){from, 0, cost*-1 , (int)G[from].size() - 1});
}

state min_cost_flow(int s,int t,int f){
  state res = state(0);
  fill( h, h+V, state(0));
  while(f > 0){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(dist,dist + V,state(INF) );
    dist[s] = state(0);
    que.push(P(dist[s],s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      int v = p.second;
      if(dist[v] < p.first)continue;
      for(int i = 0 ; i < (int)G[v].size() ; i++){
        edge &e = G[v][i];
         
        if(e.cap > 0 && dist[v] + e.cost + h[v] - h[e.to] < dist[e.to] ){
          dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(P(dist[e.to],e.to));
        }
      }
    }
    if( dist[t] == state(INF) ){
      return -1;
    }
 
    for(int v = 0 ; v < V ; v++) h[v] = h[v]+dist[v];
       
    int d = f;
    for(int v = t; v != s; v = prevv[v]){
      d = min(d,G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res = res + (h[t] * d);
    for(int v = t ; v != s ; v = prevv[v]){
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}

int N;
char c[55][55];
int main(){
  cin >> N;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      cin >> c[i][j];

  V = 2*N+2;
  int s = 2*N, t = 2*N+1;

  for(int i=0;i<N;i++){
    add_edge(s,i,1,state(0));
    add_edge(N+i,t, 1,state(0));
    for(int j=0;j<N;j++){
      add_edge(i,N+j,1, state(c[i][j]) );
    }
  }
  string alp="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  state res = min_cost_flow(s,t,N);
  for(int i=0;i<S;i++){
    for(int j=0;j<-res.v[i];j++ ){
      cout << alp[i];
    }
  }
  cout << endl;
}
### Prompt

Construct a CPP code solution to the problem outlined:

Example

Input

3
aab
czc
baa


Output

aac

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

const int INF = (1<<21);
const int MAX_V = 200;

const int S=52;

struct state{
  vector<int> v;
  state(vector<int> v): v(v) {}
  state( char c ){
    v = vector<int>(S);
    if( c <= 'Z' ) v[c-'A']=-1;
    else v[26+c-'a']=-1;
  }
  state(int x){
    v=vector<int>(S,x);
  }
  state(){}
  state operator+(const state& x) const{
    vector<int> res(v.size());
    for(int i=0;i<(int)res.size();i++)
      res[i] = v[i]+x.v[i];
    return state(res);
  }
  state operator-(const state& x){
    vector<int> res(v.size());
    for(int i=0;i<(int)res.size();i++)
      res[i] = v[i]-x.v[i];
    return state(res);
  }
  state operator*(int x){
    vector<int> res=v;
    for(int i=0;i<(int)res.size();i++) res[i]*=x;
    return res;
  }
  bool operator<(const state& x) const{
    for(int i=0;i<(int)v.size();i++){
      if( v[i] == x.v[i] ) continue;
      return v[i] < x.v[i];
    }
    return false;
  }
  bool operator==(const state& x) const{
    for(int i=0;i<x.v.size();i++)
      if( v[i] != x.v[i] ) return false;
    return true;
  }
  void view(){
    for(int i=0;i<v.size();i++){
      cout << v[i] << " ";
    }
    cout << endl;
  }
};

struct edge{
  int to, cap,rev;
  state cost;
  edge( int to, int cap, state cost, int rev) : to(to),cap(cap),cost(cost),rev(rev) {}
  edge(){}
};


typedef pair<state,int> P;

int V;
vector<edge> G[MAX_V];
state h[MAX_V];
state dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
 
void init(){
  for(int i = 0 ; i < MAX_V ; i++){
    G[i].clear();
  }
}
 
void add_edge(int from,int to,int cap,state cost){
  G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
  G[to].push_back((edge){from, 0, cost*-1 , (int)G[from].size() - 1});
}

state min_cost_flow(int s,int t,int f){
  state res = state(0);
  fill( h, h+V, state(0));
  while(f > 0){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(dist,dist + V,state(INF) );
    dist[s] = state(0);
    que.push(P(dist[s],s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      int v = p.second;
      if(dist[v] < p.first)continue;
      for(int i = 0 ; i < (int)G[v].size() ; i++){
        edge &e = G[v][i];
         
        if(e.cap > 0 && dist[v] + e.cost + h[v] - h[e.to] < dist[e.to] ){
          dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(P(dist[e.to],e.to));
        }
      }
    }
    if( dist[t] == state(INF) ){
      return -1;
    }
 
    for(int v = 0 ; v < V ; v++) h[v] = h[v]+dist[v];
       
    int d = f;
    for(int v = t; v != s; v = prevv[v]){
      d = min(d,G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res = res + (h[t] * d);
    for(int v = t ; v != s ; v = prevv[v]){
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}

int N;
char c[55][55];
int main(){
  cin >> N;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      cin >> c[i][j];

  V = 2*N+2;
  int s = 2*N, t = 2*N+1;

  for(int i=0;i<N;i++){
    add_edge(s,i,1,state(0));
    add_edge(N+i,t, 1,state(0));
    for(int j=0;j<N;j++){
      add_edge(i,N+j,1, state(c[i][j]) );
    }
  }
  string alp="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  state res = min_cost_flow(s,t,N);
  for(int i=0;i<S;i++){
    for(int j=0;j<-res.v[i];j++ ){
      cout << alp[i];
    }
  }
  cout << endl;
}
```