고양이 구스와 무작위 행렬

고양이 구스는 닉 퓨리를 위해 크기가 $n \times m$인 직사각형 표 $a$를 준비했다. 표의 각 칸에는 $0$부터 $p-1$까지의 정수가 들어 있다.

닉 퓨리는 표의 모든 수가 $0$부터 $p-1$까지의 수 중에서 서로 독립적으로, 같은 확률로 무작위 선택되었다는 것을 바로 알아챘다.

표에서 원소의 합이 $p$로 나누어떨어지는 직사각형 부분행렬을 찾으세요. 그런 부분행렬 중 합이 최대인 것을 구해야 합니다. 형식적으로는 $1 \leq i_1 \leq i_2 \leq n$, $1 \leq j_1 \leq j_2 \leq m$을 만족하고, $i_1 \leq x \leq i_2$, $j_1 \leq y \leq j_2$에 대한 $a_{x,y}$의 합이 $p$로 나누어떨어지며, 그 합이 최대인 부분행렬을 찾습니다.

첫 줄에 세 정수 $n$, $m$, $p$ ($1 \leq n \cdot m, p \leq 1\,000\,000$)가 주어진다. 각각 표의 크기와, 부분행렬의 합이 나누어떨어져야 하는 수다.

이어서 $n$개의 줄에 각각 $m$개의 정수가 주어진다. $i$번째 줄의 $j$번째 수는 $a_{i,j}$다 ($0 \leq a_{i,j} \leq p - 1$).

$a$의 각 수는 서로 독립적으로, $0$부터 $p-1$까지 중에서 같은 확률로 무작위 선택되었다고 보장된다.

합이 $p$로 나누어떨어지는 직사각형 부분행렬의 합 중 최대값을 정수 하나로 출력한다. 그런 부분행렬이 없으면 $0$을 출력한다.