该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

由于秦始皇的经费有限，本题内存只有 128MB

秦始皇委托石老板东渡瀛洲，寻找长生不老药。为了实现这个目标，必须挑选童年童女一起坐船。

现在有 $n\times n$ 个儿童组成的方阵，里面有男有女。现在有 $m$ 次询问，每个询问给出两个整数 $a,b$，查询有多少 $a$ 行 $b$ 列的矩形区域，满足四条边上的儿童全是男童。

输入格式

第一行两个整数 $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\le 100$ 。

测试点 $3,4$ 满足 $n,m\le 500$。

测试点 $5,6$ 满足 $n,m\le 1000$。

对于 $100\%$ 的数据，满足 $2\le n,m\le 1500$，$1\le a, b \le n$。

样例下载