矩形

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

注意：空间限制为 128M。

输入格式 第一行两个整数�, �。

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

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

输出格式 �行，每行一个整数表示答案。

样例输入 1 4 4 1111 1011 1111 1111 2 2 2 3 3 3 4 4

样例输出 1 5 2 1 1

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点 1,2 满足�, � ≤ 100。

测试点 3,4 满足�, � ≤ 500。 测试点 5,6 满足�, � ≤ 1000。

对于所有数据，满足 2 ≤ �, � ≤ 1500。