Longest Centered Palindrome in a Square Matrix

You are given a square matrix of characters with size \(l \times l\). You are also given \(q\) queries. In each query, you are provided with coordinates \((x_i, y_i)\) (1-indexed) which represent the center of a potential palindrome substring along either a horizontal or a vertical line in the matrix.

For a given query, you need to find the length of the longest odd-length palindrome substring centered at \((x_i, y_i)\) on the corresponding row (horizontal) or column (vertical). In other words, for each query determine the maximum between:

• The length of the longest palindrome in the row containing \(x_i\) that is centered at the \(y_i\)-th character.
• The length of the longest palindrome in the column containing \(y_i\) that is centered at the \(x_i\)-th character.

A palindrome is a string that reads the same forwards and backwards. Note that the palindrome must be centered at the given position, and only odd-length palindromes are considered.

Note: The coordinates provided in each query are 1-indexed.

inputFormat

The first line contains two integers \(l\) and \(q\) where \(l\) is the size of the square matrix and \(q\) is the number of queries.

The next \(l\) lines each contain a string of length \(l\) consisting of lowercase letters representing the matrix rows.

The following \(q\) lines each contain two integers \(x_i\) and \(y_i\) (1-indexed) indicating the center of the palindrome to be considered.

outputFormat

For each query, print a single integer in a new line representing the length of the longest palindrome (either along the row or the column) that is centered at \((x_i, y_i)\).

sample

3 2
aba
bab
aba
2 2
1 1

3
1