Cidade estreita

Time limit: 3000 msMemory limit: 256 MB

Uma cidade é uma grade com $h$ linhas e $w$ colunas. Cada célula $(i,j)$ tem um custo não negativo $a_{i,j}$ . É possível andar entre células que compartilham um lado. O custo de um caminho é a soma dos custos de suas células, incluindo as duas extremidades; se início e fim coincidem, o caminho de uma única célula tem custo igual ao dela.

Para cada consulta, determine o menor custo entre duas células. O caminho pode visitar qualquer célula da cidade, inclusive linhas fora do intervalo entre as extremidades.

Input

A primeira linha contém $h,w,q$ . Seguem $h$ linhas de $w$ custos e depois $q$ linhas com $r_1,c_1,r_2,c_2$ .

Output

Para cada consulta, imprima o menor custo.

Samples

Sample 1

Input

Output

101
5

A segunda consulta evita a célula de custo 100 e passa pela primeira coluna.