Queens High
On a d-dimensional chessboard, where each dimension has a size of N, there are K queens placed in distinct cells. A queen can move any number of squares in a straight line or along a diagonal. Specifically, a queen can move from a cell with coordinates (x_1, x_2, ..., x_d) to a cell with coordinates (x'_1, x'_2, ..., x'_d) if and only if at least one of the differences |x_i - x'_i| is non-zero, and all non-zero differences 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, meaning if one queen threatens another, the reverse is also true. Furthermore, one queen is considered to be under attack by another if the second threatens the first and all cells between them are unoccupied. This relationship is also symmetric.
Your task is to calculate the number of pairs of queens that threaten each other and the number of pairs that are under attack by each other.
Input
The first line contains three integers d, N, K (1 ≤ d ≤ 5, 1 ≤ N ≤ 1000, 0 ≤ K ≤ 40000). Each of the following K lines contains d integers x_1, ..., x_d, representing the coordinates of each queen's cell.
Output
On the first line, output the number of pairs of queens that threaten each other. On the second line, output the number of pairs of queens that are under attack by each other.