Queens High#2873
On a -dimensional chessboard, where each dimension is of size , queens are placed in different cells. A queen can move any number of squares in a straight line or along any diagonal. Specifically, a queen can move from the cell with coordinates (x_1, x_2, \dots, x_d) to the cell with coordinates (x'_1, x'_2, \dots, x'_d) if and only if at least one of the values |x_i - x'_i| is nonzero, and all nonzero values are equal. We say that one queen threatens another if there is a valid move from the first queen's cell to the second's. This relationship is symmetric: if one queen threatens another, the other also threatens the first. We say that one queen is under attack by another if the second threatens the first and all cells between them are empty. This relationship is also symmetric.
Your task is to determine the number of pairs of queens that threaten each other, and the number of pairs of queens that are under attack by each other.
The first line contains three integers , , (1 \leq d \leq 5, 1 \leq N \leq 1000, 0 \leq K \leq 40000, 1 \leq x_i \leq N). Each of the next lines contains integers x_1, \dots, x_d, representing the coordinates of each queen's cell.
On the first line, print the number of pairs of queens that threaten each other. On the second line, print the number of pairs of queens that are under attack by each other.
Esempio 1