Description
Ai is a super idol with the perfect smile.
All of her fans said that there was a star in her eye.
One day, a piece of shocking news claimed that she had become the mother of twins!
To prove this news, an easy way is to find if there is also a star in the baby's eye.
Also, because Ai's children must have the brightest star in their eyes, we need a program to automatically calculate the brightness of a star with a given picture.
Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the brightness is the summation of:
(1) A[X][j], for all 0<=j<N (The values in the Xth row)
(2) A[i][Y], for all 0<=i<N (The values in the Yth column)
(3)
A[X+i][Y+i], for all -N<=i<N if 0<=(X+i)<N and 0<=(Y+i)<N
A[X+i][Y-i], for all -N<=i<N if 0<=(X+i)<N and 0<=(Y-i)<N
(The values of two diagonals from the centers)
Note that when calculating the brightness, the value of the center points is calculated only once.
Please help her fans find the truth, or they may become very angry @@.
Hint.
If you cannot pass all the testcases, you can try to use extra arrays to record some information when you read the input data.
By doing so, you can immediately determine whether a point is a star.
Input
In this problem, with a given image (square matrix), you have to solve T solutions.
There are four parts of the input:
(1) The number of testcases, T. 1<=T<=200000
(2) The size of the square matrix, N. 1<=N<=1024
(3) An N*N matrix separated by a newline character. 0<=The values in the matrices<=N.
(4) T pairs of center points composed of 2 integers, representing the position of the center points.
Output
The brightness of each star in the matrix.
It is guaranteed that the brightness can be represented using unsigned long long datatype.
Note that you need to print "\n" in the end of each answer.