Description

Clarification

The error "Restricted Function" is cause because if you keep appending an item to an array, it will reach a limit and the OJ system will cause an error.

This is mostly caused by students who put each of the queries into an array before processing them at the end. Instead, you can just get the queries and print out the output before moving on to the next query, without storing them in an array. This is fine because OJ separated the input and output system.

Another solution is to initialize the whole array beforehand and update it without using append.

Because the old way of finding Roscaelifer was too bothersome, a new way of locating this floating city was proposed.

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 adding the following four values:

1. The maximum value in row X.

2. The maximum value in column Y.

3. The sum of all elements on the top-left to bottom-right diagonal passing through (X, Y).

4. The sum of all elements on the top-right to bottom-left diagonal passing through (X, Y).

The center element A[X][Y] is included in both diagonal sums. It is also considered when finding the maximum of its row and column. These four values are added independently; do not subtract the center element.

Hint: You can use extra arrays to record information while reading the matrix, allowing you to answer each query efficiently.

 

 

Input

• An integer T, representing the number of queries (1 ≤ T ≤ 10000).
• An integer N, representing the matrix size (1 ≤ N ≤ 250).
• N lines, each containing N integers (0 ≤ A[i][j] ≤ N).
• T lines, each containing two integers (X, Y), representing a queried position (0 ≤ X, Y < N).

Coordinates use 0-based indexing

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss