Furniture task

import java.io.*;
import java.util.*;

public class furniture {
    FastScanner in;
    PrintWriter out;

    class Job implements Comparable<Job> {
        int deadline, id;

        public Job(int deadline, int id) {
            super();
            this.deadline = deadline;
            this.id = id;
        }

        @Override
        public int compareTo(Job o) {
            return Integer.compare(deadline, o.deadline);
        }

    }

    int[][] color;
    HashMap<Integer, Integer>[] usedColorsInRows;
    HashMap<Integer, Integer>[] usedColorsInColumns;

    void conflictColumn(int x, int y, int newColor, int nextColor) {
        usedColorsInColumns[y].remove(color[x][y]);
        color[x][y] = newColor;
        usedColorsInRows[x].put(newColor, y);
        int failX = -1;
        if (usedColorsInColumns[y].containsKey(newColor)) {
            failX = usedColorsInColumns[y].get(newColor);
        }
        usedColorsInColumns[y].put(newColor, x);
        if (failX != -1) {
            conflictRow(failX, y, nextColor, newColor);
        }
    }

    void conflictRow(int x, int y, int newColor, int nextColor) {
        usedColorsInRows[x].remove(color[x][y]);
        color[x][y] = newColor;
        usedColorsInColumns[y].put(newColor, x);
        int failY = -1;
        if (usedColorsInRows[x].containsKey(newColor)) {
            failY = usedColorsInRows[x].get(newColor);
        }
        usedColorsInRows[x].put(newColor, y);
        if (failY != -1) {
            conflictColumn(x, failY, nextColor, newColor);
        }
    }

    boolean check(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            HashSet<Integer> hs = new HashSet<>();
            for (int j = 0; j < a[i].length; j++) {
                int val = a[i][j];
                if (hs.contains(val))
                    return false;
                hs.add(val);
            }
        }
        for (int j = 0; j < a[0].length; j++) {
            HashSet<Integer> hs = new HashSet<>();
            for (int i = 0; i < a.length; i++) {
                int val = a[i][j];
                if (hs.contains(val))
                    return false;
                hs.add(val);
            }
        }
        return true;
    }

    void solve2(int n, int m, int v, int[] aa) {
        Job[] a = new Job[n];
        int maxDeadline = 0;
        for (int i = 0; i < n; i++) {
            a[i] = new Job(aa[i], i);
            maxDeadline = Math.max(maxDeadline, a[i].deadline);
        }
        maxDeadline++;
        Arrays.sort(a);
        int l = -1, r = n;
        while (r - l > 1) {
            int med = (l + r) / 2;
            if (a[med].deadline < m) {
                l = med;
                continue;
            }
            int[] cnt = new int[maxDeadline];
            for (int i = med; i < n; i++) {
                for (int j = a[i].deadline - m + 1; j <= a[i].deadline; j++)
                    cnt[j]++;
            }
            while (true) {
                int lastOk = 1;
                int fail = -1;
                for (int i = 2; i < maxDeadline; i++) {
                    if (cnt[i] < m) {
                        lastOk = i;
                    } else {
                        if (cnt[i] > m) {
                            fail = i;
                            break;
                        }
                    }
                }
                if (fail == -1)
                    break;
                cnt[lastOk]++;
                cnt[fail]--;
            }
            if (cnt[1] <= m) {
                r = med;
            } else {
                l = med;
            }
        }
        out.println(r * v);
        ArrayList<Integer>[] g = new ArrayList[maxDeadline];
        for (int i = 0; i < g.length; i++)
            g[i] = new ArrayList<>();
        for (int i = r; i < n; i++) {
            for (int j = a[i].deadline - m + 1; j <= a[i].deadline; j++) {
                g[j].add(i);
            }
        }
        HashSet<Integer> hs = new HashSet<>();
        while (true) {
            int lastOk = 1;
            int fail = -1;
            for (int i = 2; i < maxDeadline; i++) {
                if (g[i].size() < m) {
                    lastOk = i;
                } else {
                    if (g[i].size() > m) {
                        fail = i;
                        break;
                    }
                }
            }
            if (fail == -1)
                break;
            hs.clear();
            for (int i : g[lastOk]) {
                hs.add(i);
            }
            for (int i = g[fail].size() - 1; i >= 0; i--) {
                if (!hs.contains(g[fail].get(i))) {
                    int xx = g[fail].get(i);
                    g[fail].remove(i);
                    g[lastOk].add(xx);
                    break;
                }
            }
        }

        int can = n - r;
        boolean[][] gg = new boolean[can][maxDeadline];
        for (int day = 0; day < maxDeadline; day++) {
            for (int x : g[day]) {
                gg[x - r][day] = true;
            }
        }
        color = new int[can][maxDeadline];
        for (int i = 0; i < color.length; i++)
            Arrays.fill(color[i], -1);
        usedColorsInRows = new HashMap[can];
        for (int i = 0; i < can; i++)
            usedColorsInRows[i] = new HashMap<>();
        usedColorsInColumns = new HashMap[maxDeadline];
        for (int i = 0; i < maxDeadline; i++)
            usedColorsInColumns[i] = new HashMap<>();
        for (int i = 0; i < can; i++)
            for (int j = 0; j < maxDeadline; j++)
                if (gg[i][j]) {
                    for (int newColor = 0; newColor < m; newColor++) {
                        if (!usedColorsInColumns[j].containsKey(newColor)) {
                            color[i][j] = newColor;
                            usedColorsInColumns[j].put(newColor, i);
                            int failY = -1;
                            if (usedColorsInRows[i].containsKey(newColor)) {
                                failY = usedColorsInRows[i].get(newColor);
                            }
                            usedColorsInRows[i].put(newColor, j);
                            if (failY != -1) {
                                for (int newColor2 = 0; newColor2 < m; newColor2++) {
                                    if (!usedColorsInRows[i]
                                            .containsKey(newColor2)) {
                                        conflictColumn(i, failY, newColor2,
                                                newColor);
                                        break;
                                    }
                                }
                            }
                            break;
                        }
                    }
                }
        int[][] ans = new int[n][m];
        for (int i = 0; i < can; i++)
            for (int j = 0; j < maxDeadline; j++)
                if (color[i][j] != -1)
                    ans[a[i + r].id][color[i][j]] = j;
        int SOME_CONST = 10000;
        for (int st = 0; st < r; st += m) {
            int cnt = Math.min(r, st + m) - st;
            for (int i = 0; i < cnt; i++)
                for (int job = 0; job < m; job++)
                    ans[a[st + i].id][job] = SOME_CONST + st + ((i + job) % m);
        }
        if (!check(ans))
            throw new AssertionError();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                out.print(ans[i][j] + " ");
            out.println();
        }

    }

    Random rnd = new Random(123);

    void solve() {
        int n = in.nextInt();
        int m = in.nextInt();
        int v = in.nextInt();
        int[] dead = new int[n];
        for (int i = 0; i < n; i++)
            dead[i] = in.nextInt();
        solve2(n, m, v, dead);


        /*
        for (int test = 0;; test++) {
            long st = System.currentTimeMillis();
            System.err.println(test);
            int n = 200;
            int m = 100;
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = rnd.nextInt(1000) + 100;
            }
            solve2(n, m, 100, a);
            System.err.println(System.currentTimeMillis() - st);
        }
        */

    }

    void run() {
        try {
            in = new FastScanner(new File("fur*iture.in"));
            out = new PrintWriter(new File("f*rniture.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    public static void main(String[] args) {
        new furniture().run();
    }
}