P4888 Triple-Removal Matrix

无

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.

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 $q$ lines. The $i$-th line should be the answer to the $i$-th query.

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