D. City of Egocentrics  

The Problem
In a certain city there live a large number of egocentrics, who in addition are eccentrics. The egocentricity means they want to live in an area where they feel they are the center of the city, and the eccentricity means they consider themselves to be the center in a very strange way.

There are four types of egocentrics: horizontal (represented by “H”), vertical (“V”), diagonal (“D”) and antidiagonal (“A”). The city is organized on a grid, and it is divided into n by n sectors, and in each sector a number of people live (an integer number between 0 and 10000). An egocentric of type H considers he is the center of the city when in the row of sectors where he lives the total number of inhabitants in the sectors in the same row on the left and on the right coincide. If the type is V, D or A, the sums to coincide are those above and under the sector where the egocentric lives, and in the same column of sectors (V), in the same diagonal (D) or antidiagonal (A). For sectors on the limits of the city, it is considered that zero people are in the direction out of the city.

Each egocentric can be of different types at the same time. So, we can have egocentrics of type H (horizontal), H D (horizontal and diagonal), or even with all the possible types: H V D A.

Because the authorities know the big problem of egocentricity in the city, they want to elaborate a list of sectors where the egocentrics can be allocated according to their egocentric types. In that way the authorities could try to allocate each egocentric in the appropriate sector, so reducing their aggressiveness.

The Input
The input begins with a line where the number of test cases (T) is indicated. The data for each test case appear in successive lines. In each test case the first line contains the size of the city (N, with maximum value 100, and the city has N by N sectors). Following there are N lines, each with N integers between 0 and 10000, separated by a space.

The Output
The output consists of a set of lines for each problem. For each problem, the sectors which accomplish the conditions for the four types of egocentricity are enumerated. The types are enumerated in the order H, V, D, A. For each city the first line is “H” and following this line appear the numbers of row and column of all the sectors which satisfy the condition for the H egocentricity. The rows and columns are numbered from 0 to N-1. Each sector appears in a line, first the number of the row, then a space, and finally the number of the column. After the H egocentricity, the V egocentricity is represented, with a line with “V” and the following lines, with each line representing a sector which satisfies the V egocentric condition. The sectors for the other egocentric types are represented in the same way, and in the order “D”, “A”. When there is no sector with this egocentric condition for a type, the line with the letter including the type appears. The sectors must appear, first those with lowest row, and for each row first those with lowest column.

Sample Input
3
3
1 2 3
4 5 6
7 8 9
3
1 1 1
1 1 1
1 1 1
4
5 7 7 6
2 4 0 8
6 1 0 7
6 8 7 5

Sample Output
H
V
D
0 2
2 0
A
0 0
2 2
H
0 1
1 1
2 1
V
1 0
1 1
1 2
D
0 2
1 1
2 0
A
0 0
1 1
2 2
H
2 2
V
1 2
2 2
D
0 3
1 1
1 2
3 0
A
0 0
2 1
2 2
3 3