Problem: You are given a grid of N rows and M columns. The square at the i-th row and j-th column will be denoted as (i,j). A nonnegative integer A_{i,j} is written for each square (i,j).

You choose some of the squares so that each row and column contains at most K chosen squares. Under this constraint, calculate the maximum value of the sum of the integers written on the chosen squares. Additionally, calculate a way to choose squares that acheives the maximum.

Constraints

* 1 \leq N \leq 50
* 1 \leq K \leq N
* 0 \leq A_{i,j} \leq 10^9
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N K
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}


Output

On the first line, print the maximum value of the sum of the integers written on the chosen squares.

On the next N lines, print a way that achieves the maximum.

Precisely, output the strings t_1,t_2,\cdots,t_N, that satisfies t_{i,j}=`X` if you choose (i,j) and t_{i,j}=`.` otherwise.

You may print any way to choose squares that maximizes the sum.

Examples

Input

3 1
5 3 2
1 4 8
7 6 9


Output

19
X..
..X
.X.


Input

3 2
10 10 1
10 10 1
1 1 10


Output

50
XX.
XX.
..X

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
const LL BIG = 1010101010;

// AtCoder Library(https://img.atcoder.jp/practice2/ac-library.zip)
// -> 一部改変(2020/09/13).
template <class Cap, class Cost> struct mcf_graph {
public:
    mcf_graph(){}
    mcf_graph(int n) : _n(n), g(n){}
    int add_edge(int from, int to, Cap cap, Cost cost){
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int m = int(pos.size());
        pos.pb({from, int(g[from].size())});
        g[from].pb(_edge{to, int(g[to].size()), cap, cost});
        g[to].pb(_edge{from, int(g[from].size()) - 1, 0, -cost});
        return m;
    }
    struct edge {
        int from, to;
        Cap cap, flow;
        Cost cost;
    };
    edge get_edge(int i){
        int m = int(pos.size());
        assert(0 <= i && i < m);
        auto _e = g[pos[i].a][pos[i].b];
        auto _re = g[_e.to][_e.rev];
        return edge{
            pos[i].a, _e.to, _e.cap + _re.cap, _re.cap, _e.cost,
        };
    }
    vector<edge> edges(){
        int m = int(pos.size());
        vector<edge> result(m);
        rep(i, m) result[i] = get_edge(i);
        return result;
    }
    pair<Cap, Cost> flow(int s, int t){
        return flow(s, t, numeric_limits<Cap>::max());
    }
    pair<Cap, Cost> flow(int s, int t, Cap flow_limit){
        return slope(s, t, flow_limit).back();
    }
    vector<pair<Cap, Cost>> slope(int s, int t){
        return slope(s, t, numeric_limits<Cap>::max());
    }
    vector<pair<Cap, Cost>> slope(int s, int t, Cap flow_limit){
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);
        vector<Cost> dual(_n, 0), dist(_n);
        vector<int> pv(_n), pe(_n);
        vector<bool> vis(_n);
        auto dual_ref = [&](){
            fill(all(dist), numeric_limits<Cost>::max());
            fill(all(pv), -1);
            fill(all(pe), -1);
            fill(all(vis), false);
            struct Q{
                Cost key;
                int to;
                bool operator<(Q r) const{ return key > r.key; }
            };
            priority_queue<Q> pq;
            dist[s] = 0;
            pq.push(Q{0, s});
            while(!pq.empty()){
                int v = pq.top().to;
                pq.pop();
                if(vis[v]) continue;
                vis[v] = true;
                if(v == t) break;
                rep(i, int(g[v].size())){
                    auto e = g[v][i];
                    if(vis[e.to] || !e.cap) continue;
                    Cost cost = e.cost - dual[e.to] + dual[v];
                    if(dist[e.to] - dist[v] > cost){
                        dist[e.to] = dist[v] + cost;
                        pv[e.to] = v;
                        pe[e.to] = i;
                        pq.push(Q{dist[e.to], e.to});
                    }
                }
            }
            if(!vis[t]) return false;
            rep(v, _n){
                if(!vis[v]) continue;
                dual[v] -= dist[t] - dist[v];
            }
            return true;
        };
        Cap flow = 0;
        Cost cost = 0, prev_cost = -1;
        vector<pair<Cap, Cost>> result;
        result.pb({flow, cost});
        while(flow < flow_limit){
            if(!dual_ref()) break;
            Cap c = flow_limit - flow;
            for(int v = t; v != s; v = pv[v]){
                c = min(c, g[pv[v]][pe[v]].cap);
            }
            for(int v = t; v != s; v = pv[v]){
                auto& e = g[pv[v]][pe[v]];
                e.cap -= c;
                g[v][e.rev].cap += c;
            }
            Cost d = -dual[s];
            flow += c;
            cost += c * d;
            if(prev_cost == d) result.pop_back();
            result.pb({flow, cost});
            prev_cost = cost;
        }
        return result;
    }
private:
    int _n;
    struct _edge{
        int to, rev;
        Cap cap;
        Cost cost;
    };
    vector<pair<int, int>> pos;
    vector<vector<_edge>> g;
};

// mincostflow.html を 参照.
int main(){
    
    int n, k;
    scanf("%d %d", &n, &k);
    /**
     * generate (s -> row -> column -> t) graph
     * i-th row correspond to vertex i
     * i-th col correspond to vertex n + i
     **/
    mcf_graph<int, LL> g(2 * n + 2);
    int s = 2 * n, t = 2 * n + 1;
    // we can "waste" the flow
    g.add_edge(s, t, n * k, BIG);
    rep(i, n){
        g.add_edge(s, i, k, 0);
        g.add_edge(n + i, t, k, 0);
    }
    rep(i, n){
        rep(j, n){
            LL a;
            scanf("%lld", &a);
            g.add_edge(i, n + j, 1, BIG - a);
        }
    }
    auto result = g.flow(s, t, n * k);
    printf("%lld\n", 1LL * n * k * BIG - result.b);
    
    vector<string> grid(n, string(n, '.'));
    auto edges = g.edges();
    for(auto e : edges){
        if(e.from == s || e.to == t || e.flow == 0) continue;
        grid[e.from][e.to - n] = 'X';
    }
    rep(i, n) printf("%s\n", grid[i].c_str());
    return 0;
    
}