给出一个 n×n 的网格，有些格子是黑色的剩下是白色的。有 m 次询问：询问网格中有多少 a 行 b 列的矩形，满足它的四条边上所有格子都是黑的。

注意：空间限制为 128M。

第一行两个整数 n, m。

接下来 n 行，每行一个长度为 n 的 01 串，0 表示白格，1 表示黑格。

接下来 m 行，每行两个数字 a, b，表示一个询问。

m 行，每行一个整数表示答案。

4 4
1111
1011
1111
1111
2 2
2 3
3 3
4 4

5
2
1
1

共 10 个测试点。
测试点 1,2 满足 n,m ≤ 100。
测试点 3,4 满足 n,m ≤ 500。
测试点 5,6 满足 n,m ≤ 1000。
对于所有数据，满足 2 ≤ n,m ≤ 1500。