Description
Roscaelifer is a bustling city in the sky, populated mostly by robots. Being in the sky, it's safe from most disasters on the ground, but it can also be very hard to find. But luckily, the city also shine bright like a star. Equipped with this information, your job now is to help us find it!
You are given an N × N matrix of integers and T queries, each query specifies a point (X, Y).
For each query, calculate the brightness of the point by summing:
-
All elements in row
X. -
All elements in column
Y. -
All elements on the top-left to bottom-right diagonal passing through
(X, Y). -
All elements on the top-right to bottom-left diagonal passing through
(X, Y).
Note: The center element A[X][Y] must only be counted once.
To better illustrate, we will show to calculate the brightness for a given matrix at a point (3,3)
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
-
An integer
T, representing the number of queries (1 ≤ T ≤ 10000). -
An integer
N, representing the matrix size (1 ≤ N ≤ 250). -
An
N × Nmatrix of integers (0 ≤ A[i][j] ≤ N). -
Tpairs of integers(X, Y), representing the queried positions.
Output
For each query, output a single integer representing the brightness of the specified point, followed by a newline.