说明

小菜给 Ocean 设计了一个小游戏。

在游戏里，地图是一个 $n \times n$ 的矩形。地图中，每个单位格子上都有一个值表示所在位置的生命体个数。

在游戏设定里，Ocean 是一个小小侦察兵，而 Ocean 的工作就是计算出从 Ocean 所在位置的左上角和右下角的生命体总数（不包括 Ocean 所在的行列） 。

请注意：作为小小侦察兵的 Ocean 是不包括在地图上的生命体个数中的。

输入格式

第一行给定两个整数 $n$ 和 $t$。 接下来 $n$ 行，每行 $n$ 个整数表示每个格子上的生命体数 $x$。 接下来的 $t$ 行，每行两个整数 $x_i$，$y_i$，表示不同时刻 Ocean 在地图上的位置。

输出格式

共 $T$ 行，每行一个整数，表示当前时刻 Ocean 所在位置的左上角和右下角的总人数。

样例

样例输入1

4 1
0 1 2 0
3 2 0 0
1 2 3 2
0 0 0 10
3 3

样例输出1

16

提示

$1 \leq n \leq 10 ^ 3$

$1 \leq t \leq 10 ^ 3$

$1 \leq x \leq 100$