Description

目前有一个N*N的矩阵，当给你一个指定的子矩阵时，请你求出子矩阵元素的和对1000求余的结果。注意矩阵中的元素N[i][j]在-32768到32767之间。

Input

输入一个整数N(1<=N<=1,000)，然后输入一个N*N的矩阵。当N为0时输入结束。 接下去输入M个子矩阵。然后M行，子矩阵的输入格式是：X1,Y1,X2,Y2分别表示矩阵中的左上角坐标和右下角坐标。X为纵坐标,Y为横坐标。最左上角坐标为（0,0）。

Output

输出子矩阵元素之和对1000求余的结果。每组Case之间一个空行。

Sample Input

3
1 2 3
4 -5 6
7 8 9
3
0 0 0 0
0 0 1 1
1 1 2 2
0

Sample Output

1
2
18

HINT

Source

NBU OJ