Submatrizes

Seja $$B_{N\times M} = \left[ \begin{array}{ccccc} b_{11} & b_{12} & b_{13} & \ldots & b_{1M} \\ b_{21} & b_{12} & b_{23} & \ldots & b_{2M} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b_{N1} & b_{N2} & b_{N3} & \ldots & b_{NM} \\ \end{array} \right]$$ uma matriz e defina a função $$f(B) = \bigoplus_{i = 1}^N\bigoplus_{j = 1}^M b_{ij},$$ onde $a\oplus b$ indica a operação “ou exclusivo” (xor) entre $a$ e $b$.

Dada uma matriz $A_{H\times W}$, determine a soma dos resultados da aplicação da função $f$, acima definida, em todas as submatrizes de $A$ de dimensões $K\times K$.

Entrada

A primeira linha da entrada contém os valores dos inteiros $H, W, K$ $(1\leq H, W\leq 2\times 10^3, 1\leq K\leq \min(H, W))$, separados por um espaço em branco.

As $H$ linhas contém, cada uma, $W$ inteiros $a_{i1}, a_{i2}, \ldots, a_{iW}$, $(0\leq a_{ij}\leq 10^9)$, separados por um espaço em branco, representando a $i$-ésima linha da matriz $A$.

Saída

Imprima, em uma linha, a soma dos resultados das aplicações de $f$ em todas as submatrizes de $A$ de dimensões $K\times K$.

Exemplo de entrada 1

2 3 2
1 3 6
2 9 5

Exemplo de saída 1

18

Explicação do exemplo 1: Há duas submatrizes $2\times 2$ de $A$, a saber $$B_1 = \left[ \begin{array}{cc} 1 & 3 \\ 2 & 9 \end{array} \right]$$ e $$B_2 = \left[ \begin{array}{cc} 3 & 6 \\ 9 & 5 \end{array} \right]$$

Temos que $f(B_1) = 1 \oplus 3 \oplus 2 \oplus 9 = 9$ e $f(B_2) = 3\oplus 6 \oplus 9 \oplus 5 = 9$, de modo que a resposta é $f(B_1) + f(B_2) = 9 + 9 = 18$.

Exemplo de entrada 2

2 2 1
1 2
3 4

Exemplo de saída 2

10

Exemplo de entrada 3

4 4 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Exemplo de saída 3

4