#P1002. 二维回文

二维回文

现在小图有个l×ll \times l的正方形字母矩阵,现在他想进行qq次询问,每次询问最长的以(xi,yi)(x_i,y_i)为中心的在一条水平或竖直的直线上的回文串的长度。

输入格式

第一行输入两个整数l,ql,q,分别表示矩阵的边长和询问的个数。

接下来的ll行,每行ll个字母,表示这个矩阵上的字母。

接下来的qq行,每行两个整数xi,yix_i,y_i,表示第ii个询问为在询问矩阵中最长的以(xi,yi)(x_i,y_i)为中心的在一条直线上的回文串的长度。

输出格式

输出qq行,第ii行为对于第ii个询问的回答。

样例

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

数据范围

对于20%20\%的数据,1l21 \le l \le 2

另有20%20\%的数据,q=1q = 1

另有20%20\%的数据,字母矩阵中心对称,上下对称,左右对称且对角线对称。

对于100%100\%的数据,1l,q20001 \le l,q \le 2000,字母只有小写字母。