Alpinistlər

"'markdown Çili Andları, yürüyüş və piyada gəzintilər üçün getdikcə daha populyar bir məkan halına gəlir. Andların bir çox hissəsi olduqca uzaq və buna görə də təhlükəlidir. Bu səbəbdən Turizm Nazirliyi səyahətçilərə səfərlərini planlaşdırmaqda kömək etmək istəyir. Xüsusilə, səyahətçilər səfərləri zamanı nə qədər yüksəlməli olduqlarını bilməlidirlər, çünki bu məlumat onlara hansı avadanlıqları götürməli olduqlarına qərar verməyə kömək edəcək. Nazirlik sizə yeni başlayan alpinistlərə bu məlumatı təqdim etməyi tapşırıb.

Sizə Andların bir hissəsinin topoqrafik xəritəsi, yüksəklik dəyərlərinin ikiölçülü şəbəkəsi şəklində təqdim olunur, həmçinin başlanğıc və təyinat nöqtələrinin siyahısı verilir. Alpinistlər şəbəkənin hər bir hüceyrəsindən dörd qonşu hüceyrəyə keçə bilərlər. Hər bir alpinist üçün səfərlərini başa çatdırmaq üçün çatmalı olduqları minimum hündürlüyü tapın.

Giriş verilənləri

Birinci sətirdə üç tam ədəd $m,n$ və $q(1\le m,n\le 500,1\le q\le 10^5)$ yazılıb, burada $m$ — sətirlərin sayı, $n$ — sütunların sayı və $q$ — alpinistlərin sayıdır.

Növbəti $m$ sətirin hər biri xəritədəki yüksəklik dəyərləri olan $n$ tam ədəd $h_1,...,h_n(1\le h_i\le 10^6)$ ehtiva edir;

Növbəti $q$ sətirin hər biri $(x_1,y_1)$ nöqtəsindən $(x_2,y_2)$ nöqtəsinə yürüyüş etmək istəyən alpinisti təsvir edən dörd tam ədəd $x_1,y_1,x_2,y_2(1\le x_1,x_2\le m;1\le y_1,y_2\le n)$ ehtiva edir.

Şəbəkənin sol üst hüceyrəsi $(1,1)$ koordinatlarına, sağ alt hüceyrəsi isə $(m,n)$ koordinatlarına malikdir.

Çıxış verilənləri

$q$ tam ədəd çıxarın — giriş məlumatları ilə eyni ardıcıllıqla hər bir alpinist üçün minimum hündürlük. "'

Nümunələr