Problem: Owl Sonya gave a huge lake puzzle of size n × m to hedgehog Filya as a birthday present. Friends immediately started to assemble the puzzle, but some parts of it turned out to be empty — there was no picture on them. Parts with picture on it are denoted by 1, while empty parts are denoted by 0. Rows of the puzzle are numbered from top to bottom with integers from 1 to n, while columns are numbered from left to right with integers from 1 to m.

Animals decided to complete the picture and play with it, as it might be even more fun! Owl and hedgehog ask each other some queries. Each query is provided by four integers x1, y1, x2, y2 which define the rectangle, where (x1, y1) stands for the coordinates of the up left cell of the rectangle, while (x2, y2) stands for the coordinates of the bottom right cell. The answer to the query is the size of the maximum square consisting of picture parts only (only parts denoted by 1) and located fully inside the query rectangle.

Help Sonya and Filya answer t queries.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1000) — sizes of the puzzle.

Each of the following n lines contains m integers aij. Each of them is equal to 1 if the corresponding cell contains a picture and 0 if it's empty.

Next line contains an integer t (1 ≤ t ≤ 1 000 000) — the number of queries.

Then follow t lines with queries' descriptions. Each of them contains four integers x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — coordinates of the up left and bottom right cells of the query rectangle.

Output

Print t lines. The i-th of them should contain the maximum size of the square consisting of 1-s and lying fully inside the query rectangle.

Example

Input

3 4
1 1 0 1
0 1 1 0
0 1 1 0
5
1 1 2 3
2 1 3 2
3 2 3 4
1 1 3 4
1 2 3 4


Output

1
1
1
2
2

Solution (in JAVA):

Solution:
import java.io.BufferedInputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.function.IntBinaryOperator;

public class CF713D {


	private static final class SparseTable2D {
		private int n; // rows
		private int m; // cols
		private byte log2N;
		private byte log2M;
		private IntBinaryOperator func;

		private short[][][][] st;

		SparseTable2D(short[][] t, IntBinaryOperator fn) {
			n = t.length;
			m = t[0].length;
			func = fn;

			log2N = Log2.TBL[n];
			log2M = Log2.TBL[m];

			st = new short[log2N+1][log2M+1][][];

			st[0][0] = t;

			for (int log2x = 1; log2x <= log2M; log2x++) {
				int stepX = 1 << (log2x - 1);
				int sizeX = m - (1 << log2x) + 1;

				short[][] tmp = new short[n][sizeX];
				short[][] prev = st[0][log2x - 1];

				st[0][log2x] = tmp;
				for (int y = 0; y < n; y++) {
					for (int x = 0; x < sizeX; x++) {
						tmp[y][x] = (short) func.applyAsInt(prev[y][x], prev[y][x + stepX]);
					}
				}
			}

			for (int log2y = 1; log2y <= log2N; log2y++) {
				int stepY = 1 << (log2y - 1);
				int sizeY = n - (1 << log2y) + 1;

				short[][] tmp = new short[sizeY][m];
				short[][] prev = st[log2y - 1][0];

				st[log2y][0] = tmp;
				for (int y = 0; y < sizeY; y++) {
					for (int x = 0; x < m; x++) {
						tmp[y][x] = (short) func.applyAsInt(prev[y][x], prev[y + stepY][x]);
					}
				}
			}

			for (int log2y = 1; log2y <= log2N; log2y++) {
				int stepY = 1 << (log2y - 1);
				int sizeY = n - (1 << log2y) + 1;

				for (int log2x = 1; log2x <= log2M; log2x++) {
					int stepX = 1 << (log2x - 1);
					int sizeX = m - (1 << log2x) + 1;

					short[][] tmp = new short[sizeY][sizeX];
					st[log2y][log2x] = tmp;

					short[][] prev = st[log2y - 1][log2x - 1];

					for (int y = 0; y < sizeY; y++) {
						for (int x = 0; x < sizeX; x++) {
							tmp[y][x] = (short) func.applyAsInt(func.applyAsInt(prev[y][x], prev[y + stepY][x]), func.applyAsInt(prev[y + stepY][x + stepX], prev[y][x + stepX]));
						}
					}
				}
			}
		}


		public int calculate(int x1, int y1, int x2, int y2) {
			int log2x = Log2.TBL[x2 - x1 + 1];
			int log2y = Log2.TBL[y2 - y1 + 1];
			int stepX = 1 << log2x;
			int stepY = 1 << log2y;

			short[][] tmp = st[log2y][log2x];

			return func.applyAsInt(
					func.applyAsInt(tmp[y1][x1], tmp[y1][x2 - stepX + 1]),
					func.applyAsInt(tmp[y2 - stepY + 1][x1], tmp[y2 - stepY + 1][x2 - stepX + 1])
			);
		}

	}

	static final class Log2 {
		static byte[] TBL;

		static void init(int upper) {
			byte lg = 0;
			int n = 2, i = 0;
			TBL = new byte[upper + 1];
			do {
				while (i < n && i <= upper) TBL[i++] = lg;
				n = n << 1;
				lg++;
			} while (i <= upper);
		}
	}

	private static SparseTable2D sparseTable2D;

	private static int findMaxSquareBruteForce(short x1, short y1, short x2, short y2) {
		short[][] pp = sparseTable2D.st[0][0];
		int result = 0;
		for (short x = x1; x <= x2; x++) {
			for (short y = y1; y <= y2; y++) {
				result = Math.max(Math.min(Math.min(pp[y][x], x2 - x + 1), y2 - y + 1), result);
			}
		}
		return result;
	}

	private static int findMaxSquare(int x1, int y1, int x2, int y2) {
		int maxResult = Math.min(x2 - x1 + 1, y2 - y1 + 1);
		int minResult = 0;

		while (maxResult != minResult) {
			int mm = maxResult + minResult;
			int r = (mm >> 1) + (mm & 1);
			int max = sparseTable2D.calculate(x1, y1, x2 - r + 1, y2 - r + 1);
			if (max > r) {
				minResult = r;
			} else if (max < r) {
				maxResult = r - 1;
			} else {
				return r;
			}
		}
		return maxResult;
	}

	static QScanner scanner;
	static PrintWriter writer;

	public static void main(String[] args) throws IOException {
		Log2.init(1000);

		scanner = new QScanner();
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

		int n = scanner.nextInt(), m = scanner.nextInt();
		short[][] pp = new short[n][m];

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++) {
				pp[y][x] = (short) scanner.nextInt();
			}
		}


		for (int y = n - 1; y > 0; y--) {
			for (int x = m - 1; x > 0; x--) {
				if (pp[y - 1][x - 1] > 0) {
					pp[y - 1][x - 1] += Math.min(Math.min(pp[y][x], pp[y - 1][x]), pp[y][x - 1]);
				}
			}
		}

		sparseTable2D = new SparseTable2D(pp, Math::max);

		int t = scanner.nextInt();
		for (int i = 0; i < t; i++) {
			int y1 = scanner.nextInt() - 1, x1 = scanner.nextInt() - 1, y2 = scanner.nextInt() - 1, x2 = scanner.nextInt() - 1;
			writer.println(findMaxSquare(x1, y1, x2, y2));
		}


		writer.close();
		//test(n, m);
	}


	private static void test(int pN, int pM) {
		long d1 = 0;
		long d2 = 0;

		for (short x1 = 0; x1 < pN; x1++) {
			for (short x2 = x1; x2 < pN; x2++) {
				for (short y1 = 0; y1 < pM; y1++) {
					for (short y2 = y1; y2 < pM; y2++) {
						long t1 = System.nanoTime();
						int v1 = findMaxSquareBruteForce(x1, y1, x2, y2);
						long t2 = System.nanoTime();
						int v2 = findMaxSquare(x1, y1, x2, y2);
						long t3 = System.nanoTime();
						if (v1 != v2) {
							System.out.println((x1 + 1) + ":" + (y1 + 1) + "-" + (x2 + 1) + ":" + (y2 + 1) + "[" + v1 + "/" + v2 + "]");
						}
						d1 += (t2 - t1);
						d2 += (t3 - t2);
					}
				}
			}
		}

		System.out.println(d1);
		System.out.println(d2);
	}


	static class QScanner {
		Reader r = new InputStreamReader(new BufferedInputStream(System.in));

		int nextInt() throws IOException {
			boolean minus = false;
			int result = 0;

			int c = r.read();
			while (c != -1 && !((c >= '0' && c <= '9') || c == '-')) {
				c = r.read();
			}

			if (c == '-') {
				minus = true;
				c = r.read();
			}

			while (c >= '0' && c <= '9') {
				result = result * 10 + (c - '0');
				c = r.read();
			}

			return minus ? -result : result;
		}

	}


}