Problem Description

Now Little Y has an $l \times l$ square letter matrix. He wants to make $q$ queries. For each query, find the maximum length of a palindrome string centered at $(x_i, y_i)$ that lies on a single horizontal or vertical line.

Input Format

The first line contains two integers $l, q$, representing the side length of the matrix and the number of queries.

The next $l$ lines each contain $l$ letters, representing the letters in the matrix.

The next $q$ lines each contain two integers $x_i, y_i$, representing the $i$-th query: ask for the maximum length of a palindrome centered at $(x_i, y_i)$ that lies on a single straight line in the matrix.

Output Format

Output $q$ lines. The $i$-th line should be the answer to the $i$-th query.

5 5
abcba
bcdcb
cdedc
bcdcb
abcba
1 1
1 2
1 3
2 3
3 3

1
1
5
5
5

Hint

For $20\%$ of the testdata, $1 \le l \le 2$.

Another $20\%$ of the testdata has $q = 1$.

Another $20\%$ of the testdata has a letter matrix that is centrally symmetric, vertically symmetric, horizontally symmetric, and diagonally symmetric.

For $100\%$ of the testdata, $1 \le l, q \le 2000$, and the letters are lowercase only.

Translated by ChatGPT 5