Grapevine

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

You are given an $N\times M$ height matrix. Values are non-decreasing from left to right in each row and from top to bottom in each column.

For each query interval $[L,U]$, find the largest side length of a contiguous square submatrix whose every value satisfies $L\le H_{i,j}\le U$.

Input

The first line contains $N$ and $M$.

The next $N$ lines contain the matrix.

The next line contains $Q$.

The next $Q$ lines contain $L$ and $U$.

Output

For each query, print the maximum valid square side length. Print 0 if no cell is valid.

Subtasks

• Subtask 1 — 20%: $N,M\le40$, $Q\le100$.
• Subtask 2 — 30%: $N,M\le200$, $Q\le1000$.
• Subtask 3 — 50%: $N,M\le500$, $Q\le10000$.

All matrix values and query bounds are between $0$ and $10^5$.

Examples

Input

4 5
13 21 25 33 34
16 21 33 35 35
16 33 33 45 50
23 51 66 83 93
3
22 90
33 35
20 100

Output

3
2
4

Explanation

For $[22,90]$, a valid square of side $3$ exists, but no valid square of side $4$ exists.