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

Description

小华喜欢在夜晚仰望星空，并把星空想象成一个巨大的二维平面，坐标从 (0,0) 到 (N-1, N-1)。 有些位置有星星，有些位置没有。 为了记录星星的分布，小华绘制了一张 N × N 的星图，用 1 表示该位置有星星，0 表示没有星星。 现在，小华想知道，在星图的某个矩形区域里，有多少颗星星。给你一个 N × N 的矩阵 sky[][]，表示星图。 然后会有 Q 次询问，每次询问给出矩形区域的左上角 (x1, y1) 和右下角 (x2, y2)， 要求输出这个矩形内的星星总数。

Format

Input

第一行整数N（1<=N<=1000) 接下来N行，每行N个整数，0或1，表示星图 接下来Q行，每行四个整数，x1,x2,y1,y2, (1 <= Q <= 1000，0 <= x1<= x2 < N，0<= y1<= y2 < N）

Output

输出Q行，每行输出一个整数，表示矩形内的星星数量

Samples

5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2
4 4 2 3
1 4 3 3

0
0

Limitation

1s, 1024KiB for each test case.