三去矩阵
题目背景
无
题目描述
现在小Y有个$l \times l$的正方形字母矩阵,现在他想进行$q$次询问,每次询问最长的以$(x_i,y_i)$为中心的在一条水平或竖直的直线上的回文串的长度。
输入输出格式
输入格式
第一行输入两个整数$l,q$,分别表示矩阵的边长和询问的个数。
接下来的$l$行,每行$l$个字母,表示这个矩阵上的字母。
接下来的$q$行,每行两个整数$x_i,y_i$,表示第$i$个询问为在询问矩阵中最长的以$(x_i,y_i)$为中心的在一条直线上的回文串的长度。
输出格式
输出$q$行,第$i$行为对于第$i$个询问的回答。
输入输出样例
输入样例 #1
5 5
abcba
bcdcb
cdedc
bcdcb
abcba
1 1
1 2
1 3
2 3
3 3
输出样例 #1
1
1
5
5
5
说明
对于$20\%$的数据,$1 \le l \le 2$
另有$20\%$的数据,$q = 1$
另有$20\%$的数据,字母矩阵中心对称,上下对称,左右对称且对角线对称。
对于$100\%$的数据,$1 \le l,q \le 2000$,字母只有小写字母。