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

class Matrix
{
	public final int w, h;
	public final int[] raw;

	public Matrix(int w, int h) {
		validateSize(w, h);
		this.w = w;
		this.h = h;
		raw = new int[w * h];
	}

	public static Matrix explicit(int w, int h, int... cells) {
		if (cells.length != w * h)
			throw new IllegalArgumentException(String.format("Expected %d values of %d×%d matrix, got %d.", w*h, w, h, cells.length));
		Matrix r = new Matrix(w, h);
		System.arraycopy(cells, 0, r.raw, 0, cells.length);
		return r;
	}

	public String toString() {
		String[] reprs = new String[raw.length];
		int maxLen = 0;
		for (int i = 0; i < reprs.length; i++) {
			reprs[i] = Integer.toString(raw[i]);
			maxLen = Math.max(maxLen, reprs[i].length());
		}
		String fmt = "%" + maxLen + "s";

		StringBuilder rsb = new StringBuilder();
		for (int y = 0, absIdx = 0; y < h; y++) {
			for (int x = 0; x < w; x++, absIdx++) {
				rsb.append(String.format(fmt, reprs[absIdx])).append(x + 1 < w ? " " : y + 1 < h ? "\n" : "");
			}
		}
		return rsb.toString();
	}

	public static void validateSize(int w, int h) {
		if (w <= 0 || h <= 0)
			throw new IllegalArgumentException(String.format("Bad matrix size: %d×%d.", w, h));
	}

	public void validateSubmatrix(int x, int y, int w, int h) {
		validateSize(w, h);
		if (x < 0 || y < 0 || x + w > this.w || y + h > this.h)
			throw new IllegalArgumentException(String.format("Bad submatrix of %d×%d: (%d, %d) + %d×%d.", this.w, this.h, x, y, w, h));
	}

	public int absoluteIndex(int x, int y) {
		if (x < 0 || y < 0 || x >= w || y >= h)
			throw new IllegalArgumentException(String.format("Bad cell of %d×%d: (%d, %d).", w, h, x, y));
		return y * w + x;
	}

	static Matrix prepareMultiply(
		Matrix a, int ax, int ay, int aw, int ah,
		Matrix b, int bx, int by, int bw, int bh,
		Matrix r) {

		a.validateSubmatrix(ax, ay, aw, ah);
		b.validateSubmatrix(bx, by, bw, bh);
		if (aw != bh)
			throw new IllegalArgumentException(String.format("Matrices of %d×%d and %d×%d cannot be multiplied: number of columns of the first must match the number of rows of the second.", aw, ah, bw, bh));

		if (r == null) {
			r = new Matrix(bw, ah);
		} else if (r.w != bw || r.h != ah) {
			throw new IllegalArgumentException(String.format("Bad resulting matrix size: expected %d×%d, got %d×%d.", bw, ah, r.w, r.h));
		}
		return r;
	}

	public static Matrix multiply_AiVer(
		Matrix a, int ax, int ay, int aw, int ah,
		Matrix b, int bx, int by, int bw, int bh,
		Matrix r) {

		r = prepareMultiply(a, ax, ay, aw, ah, b, bx, by, bw, bh, r);

		int aRowStartAbsIdx = a.absoluteIndex(ax, ay); // points to the beginning of the current row of A, i. e. A[0, y].
		int bColStartAbsIdx = b.absoluteIndex(bx, by); // points to the beginning of the current column of B, i. e. B[x, 0].

		// result cell (x, y) (pointed by rAbsIdx) gets the dot product of current row of A and current column of B.
		for (int y = 0, rAbsIdx = 0; y < r.h; y++, aRowStartAbsIdx += a.w, bColStartAbsIdx -= r.w) {
			for (int x = 0; x < r.w; x++, rAbsIdx++, bColStartAbsIdx++) {
				int dot = 0;
				for (int i = 0, aAbsIdx = aRowStartAbsIdx, bAbsIdx = bColStartAbsIdx; i < aw; i++, aAbsIdx++, bAbsIdx += b.w) {
					dot += a.raw[aAbsIdx] * b.raw[bAbsIdx];
				}
				r.raw[rAbsIdx] = dot;
			}
		}
		return r;
	}

	public Matrix multiply_AiVer(Matrix b) {
		return multiply_AiVer(this, 0, 0, w, h, b, 0, 0, b.w, b.h, null);
	}

	int get(int x, int y) {
		return raw[y * w + x];
	}

	void set(int x, int y, int value) {
		raw[y * w + x] = value;
	}

	public static Matrix multiply_GsVer(
		Matrix a, int ax, int ay, int aw, int ah,
		Matrix b, int bx, int by, int bw, int bh,
		Matrix r) {

		r = prepareMultiply(a, ax, ay, aw, ah, b, bx, by, bw, bh, r);

		for (int y = 0; y < r.h; y++) {
			for (int x = 0; x < r.w; x++) {
				int dot = 0;
				for (int i = 0; i < aw; i++) {
					dot += a.get(i, y) * b.get(x, i);
				}
				r.set(x, y, dot);
			}
		}
		return r;
	}

	public Matrix multiply_GsVer(Matrix b) {
		return multiply_GsVer(this, 0, 0, w, h, b, 0, 0, b.w, b.h, null);
	}

	@Override
	public boolean equals(Object other) {
		if (this == other) return true;
		if (this.getClass() != other.getClass()) return false;
		Matrix om = (Matrix) other;
		return w == om.w && h == om.h && Arrays.equals(raw, om.raw);
	}

	// just for resulting matrices to not be subjected to dead store elimination.
	public int elementsSum() {
		int sum = 0;
		for (int i = 0; i < raw.length; i++) {
			sum += raw[i];
		}
		return sum;
	}
}

class Ideone
{
	static void test() {
		// www.mathwarehouse.com/algebra/matrix/images/product-matrix2.png
		Matrix
			a = Matrix.explicit(4, 2,
				1, 4, 6, 10,
				2, 7, 5, 3),

			b = Matrix.explicit(3, 4,
				1, 4, 6,
				2, 7, 5,
				9, 0, 11,
				3, 1, 0),

			expected = Matrix.explicit(3, 2,
				93, 42, 92,
				70, 60, 102),
				
			abProd_AiVer = a.multiply_AiVer(b),
			abProd_GsVer = a.multiply_GsVer(b);

		if (!abProd_AiVer.equals(expected)) throw new RuntimeException(String.format("bad Matrix.multiply_AiVer: got\n%s\nexpected\n%s.", abProd_AiVer, expected));
		if (!abProd_GsVer.equals(expected)) throw new RuntimeException(String.format("bad Matrix.multiply_GsVer: got\n%s\nexpected\n%s.", abProd_GsVer, expected));
	}

	static void benchmark() {
		Matrix a = new Matrix(1000, 500);
		Matrix b = new Matrix(600, 1000);
		Matrix r = new Matrix(600, 500); // so allocation won't happen during time measurement

		long start_AiVer = System.nanoTime();
		Matrix.multiply_AiVer(a, 0, 0, a.w, a.h, b, 0, 0, b.w, b.h, r);
		double time_AiVer = (System.nanoTime() - start_AiVer) * 1e-9;
		System.out.println(String.format("Multiplication using absolute indices: %.2f s", time_AiVer, r.elementsSum()));

		long start_GsVer = System.nanoTime();
		Matrix.multiply_GsVer(a, 0, 0, a.w, a.h, b, 0, 0, b.w, b.h, r);
		double time_GsVer = (System.nanoTime() - start_GsVer) * 1e-9;
		System.out.println(String.format("Multiplication using .get()/.set(): %.2f s (%s)", time_GsVer, judgement(time_GsVer, time_AiVer), r.elementsSum()));
	}
	
	static String judgement(double time, double refTime) {
		final double absThreshold = 0.1, relThreshold = .05;

		return time <= absThreshold || refTime <= absThreshold ?
			String.format("can't judge, min. required time is %.1f s", absThreshold) :
			Math.max(time, refTime) > (1 + relThreshold) * Math.min(time, refTime) ?
			String.format("%.0f%% %s", Math.abs(time / refTime - 1) * 100, time < refTime ? "faster" : "slower") :
			String.format("no observable difference, min. %.0f%% required", relThreshold * 100);
	}

	public static void main (String[] args)
	{
		try {
			test();
			benchmark();
		} catch (Exception e) {
			System.out.println(e);
		}
	}
}