import java.io.File;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

class Brett {
	class Rute {
		int verdi;
		Rad rad;
		Kolonne kolonne;
		Boks boks;
		Brett brett;

		Rute neste = null;

		Rute(int verdi, Brett brett) {
			this.verdi = verdi;
			this.brett = brett;
		}

		public boolean harVerdi() {
			return verdi != -1;
		}

		public int[] finnAlleMuligeTall() {
			ArrayList<Integer> ugyldige = new ArrayList<>();

			for (Rute r: rad.ruter) {
				if (r.harVerdi()) {
					ugyldige.add(r.verdi);
				}
			}
			for (Rute r: kolonne.ruter) {
				if (r.harVerdi()) {
					ugyldige.add(r.verdi);
				}
			}
			for (Rute r: boks.ruter) {
				if (r.harVerdi()) {
					ugyldige.add(r.verdi);
				}
			}

			ArrayList<Integer> gyldige = new ArrayList<>();
			for (int i = 1; i <= brett.storrelse; ++i) {
				if (!ugyldige.contains(i)) {
					gyldige.add(i);
				}
			}

			int[] res = new int[gyldige.size()];
			for (int i = 0; i < res.length; ++i) {
				res[i] = gyldige.get(i);
			}
			return (int[])res;
		}

		/*
		 * fyllUtDenneRuteOgResten
		 * Jeg ga den et annet navn, som jeg mener er bedre. Maalet er ikke
		 * aa fylle ut ruten, men aa finne losninger.
		 */
		public List<List<Integer>> finnLosning() {

			// Bare skip denne ruten hvis vi har en verdi; ingenting aa lose
			if (harVerdi()) {
				List<List<Integer>> losninger;
				if (neste != null) {
					losninger = neste.finnLosning();
				} else {
					losninger = new ArrayList<>();
					losninger.add(new ArrayList<>());
				}
				for (List<Integer> losning: losninger) {
					losning.add(verdi);
				}
				return losninger;
			}

			List<List<Integer>> losninger = new ArrayList<>();
			int[] mulige = finnAlleMuligeTall();
			for (int mulig: mulige) {
				verdi = mulig;

				List<List<Integer>> nestesLosninger;
				if (neste == null) {
					nestesLosninger = new ArrayList<>();
					List<Integer> l = new ArrayList<Integer>();
					nestesLosninger.add(l);
				} else {
					nestesLosninger = neste.finnLosning();
				}

				for (List<Integer> l: nestesLosninger) {
					l.add(verdi);
					losninger.add(l);
				}
			}
			verdi = -1;

			return losninger;
		}
	}

	class Kolonne {
		private int index = 0;
		Rute[] ruter;

		Kolonne(int storrelse) {
			ruter = new Rute[storrelse];
		}

		public void settInn(Rute r) {
			ruter[index++] = r;
		}
	}

	class Rad {
		private int index = 0;
		Rute[] ruter;

		Rad(int storrelse) {
			ruter = new Rute[storrelse];
		}

		public void settInn(Rute r) {
			ruter[index++] = r;
		}
	}

	class Boks {
		private int index = 0;
		Rute[] ruter;
		int bredde;
		int hoyde;

		Boks(int bredde, int hoyde) {
			this.bredde = bredde;
			this.hoyde = hoyde;
			ruter = new Rute[bredde * hoyde];
		}

		public void settInn(Rute r) {
			ruter[index++] = r;
		}
	}

	File fil;
	int raderPerBoks;
	int kolonnerPerBoks;
	int antallBokserX;
	int antallBokserY;
	int storrelse;

	Rute[] ruter;
	Rad[] rader;
	Kolonne[] kolonner;
	Boks[] bokser;

	Brett(File fil) throws Exception {
		this.fil = fil;
		read();
	}

	public SudokuBeholder los() {
		List<List<Integer>> losninger = ruter[0].finnLosning();
		SudokuBeholder sb = new SudokuBeholder(this);

		for (List<Integer> losning: losninger) {
			SudokuBeholder.Losning l = new SudokuBeholder.Losning();
			for (int i = losning.size() - 1; i >= 0; --i) {
				Rute r = ruter[losning.size() - 1 - i];
				l.leggTil(losning.get(i), r.harVerdi());
			}
			sb.leggTil(l);
		}

		return sb;
	}

	public SudokuBeholder.Losning tilLosning() {
		SudokuBeholder.Losning losning = new SudokuBeholder.Losning();
		for (Rute r: ruter) {
			losning.leggTil(r.verdi, r.harVerdi());
		}
		return losning;
	}


	public void print() throws Exception {
		int x = 0;
		int y = 1;
		int modX = storrelse / antallBokserX;
		int modY = storrelse / antallBokserY;

		for (Rute r: ruter) {
			if (x % modX == 0 && x != 0) {
				System.out.print("|");
			}

			if (r.harVerdi()) {
				System.out.print(toChar(r.verdi));
			} else {
				System.out.print(" ");
			}

			x += 1;
			if (x >= storrelse) {
				x = 0;

				if (y % modY == 0 && y < storrelse) {
					System.out.println("");
					for (int i = 0; i < storrelse; ++i) {
						if (i %  modX == 0 && i != 0) {
							System.out.print("+");
						}
						System.out.print("-");
					}
				}
				System.out.println("");
				y += 1;
			}
		}
	}

	public int toInt(char c) throws Exception {
		if (c == '.') {
			return -1;
		} else if (c >= '1' && c <= '9') {
			return (int)c - 49 + 1;
		} else if (c >= 'A' && c <= 'Z') {
			return (int)c - 65 + 10;
		} else if (c == '@') {
			return 36;
		} else if (c == '#') {
			return 37;
		} else if (c == '&') {
			return 38;
		} else if (c >= 'a' && c <= 'z') {
			return c - 97 + 39;
		} else {
			throw new IllegalArgumentException();
		}
	}

	public char toChar(int c) throws Exception {
		if (c == -1) {
			return '.';
		} else if (c >= 1 && c <= 9) {
			return (char)(c + 49 -1);
		} else if (c >= 10 && c <= 35) {
			return (char)(c + 65 - 10);
		} else if (c == 36) {
			return '@';
		} else if (c == 37) {
			return '#';
		} else if (c == 38) {
			return '&';
		} else if (c >= 39 && c <= 64) {
			return (char)(c + 97 - 39);
		} else {
			throw new IllegalArgumentException();
		}
	}

	private void read() throws Exception {
		Scanner s = new Scanner(fil);

		try {
			raderPerBoks = Integer.parseInt(s.nextLine());
			kolonnerPerBoks = Integer.parseInt(s.nextLine());
		} catch (Exception ex) {
			throw new Exception("Filen starter ikke med dimensjoner!");
		}

		try {
			storrelse = raderPerBoks * kolonnerPerBoks;
			antallBokserX = storrelse / kolonnerPerBoks;
			antallBokserY = storrelse / raderPerBoks;
		} catch (Exception ex) {
			throw new Exception("Filen inneholder feil!");
		}

		if (storrelse > 64) {
			throw new Exception("For stort brett!");
		}

		ruter = new Rute[storrelse * storrelse];

		// Les inn alle ruter
		int i = 0;
		Rute forrige = null;
		for (int y = 0; y < storrelse; ++y) {
			if (!s.hasNextLine()) {
				throw new Exception("For faa rader!");
			}

			char[] rad = s.nextLine().toCharArray();
			if (rad.length > storrelse) {
				throw new Exception("For mange kolonner i rad "+(y+1)+"!");
			}

			for (int x = 0; x < storrelse; ++x) {
				char c;
				try {
					c = rad[x];
				} catch (ArrayIndexOutOfBoundsException ex) {
					throw new Exception("For faa kolonner i rad "+(y+1)+"!");
				}

				Rute r = new Rute(toInt(c), this);
				if (forrige != null) {
					forrige.neste = r;
				}
				ruter[i++] = r;
				forrige = r;
			}
		}
		if (s.hasNextLine()) {
			throw new Exception("For mange rader!");
		}

		// Opprett rader, kolonner, og bokser
		// (obligens `void opprettDatastruktur()`, jeg mener det ikke gir mening
		//   aa ha det som en egen metode, da det vil skje hvis og bare hvis vi
		//   leser inn ny informasjon)

		rader = new Rad[storrelse];
		kolonner = new Kolonne[storrelse];
		bokser = new Boks[storrelse];
		for (i = 0; i < storrelse; ++i) {
			rader[i] = new Rad(storrelse);
			kolonner[i] = new Kolonne(storrelse);
			bokser[i] = new Boks(kolonnerPerBoks, raderPerBoks);
		}

		int x = 0;
		int y = 0;
		for (Rute r: ruter) {
			r.rad = rader[y];
			rader[y].settInn(r);
			r.kolonne = kolonner[x];
			kolonner[x].settInn(r);

			int boxx = (x / kolonnerPerBoks) % antallBokserX;
			int boxy = (y / raderPerBoks) % antallBokserY;
			int boxi = boxx + (boxy * antallBokserX);
			bokser[boxi].settInn(r);
			r.boks = bokser[boxi];

			x += 1;
			if (x >= storrelse) {
				x = 0;
				y += 1;
			}
		}
	}
}