Альпіністи

Чилійські Анди стають все більш популярним напрямком для походів і пішохідних прогулянок. Багато частин Анд є досить віддаленими і, відповідно, небезпечними. Через це Міністерство туризму хоче допомогти мандрівникам спланувати свої поїздки. Зокрема, мандрівникам необхідно знати, наскільки їм доведеться підніматися під час своєї подорожі, оскільки ця інформація допоможе їм вирішити, яке обладнання слід взяти з собою. Міністерство доручило Вам надати початківцям альпіністам цю інформацію.

Вам надано топографічну карту частини Анд, представлену у вигляді двовимірної сітки значень висот, а також список точок відправлення та пунктів призначення. Альпіністи можуть переміщатися з кожної комірки сітки в будь-яку з чотирьох сусідніх комірок. Для кожного альпініста знайдіть мінімальну висоту, яку йому слід досягти, щоб завершити свою подорож.

Вхідні дані

У першому рядку записані три цілі числа $m,n$ і $q(1\le m,n\le 500,1\le q\le 10^5)$, де $m$ — кількість рядків, $n$ — кількість стовпців, а $q$ — кількість альпіністів.

Кожен з наступних $m$ рядків містить $n$ цілих чисел $h_1,...,h_n(1\le h_i\le 10^6)$ — значення висот на карті;

Кожен з наступних $q$ рядків містить чотири цілі числа $x_1,y_1,x_2,y_2(1\le x_1,x_2\le m;1\le y_1,y_2\le n)$, що описують альпініста, який бажає здійснити похід від $(x_1,y_1)$ до $(x_2,y_2)$.

Верхня ліва комірка сітки має координати $(1,1)$, а нижня права комірка має координати $(m,n)$.

Вихідні дані

Виведіть $q$ цілих чисел — мінімальну висоту для кожного альпініста в тому ж порядку, що і у вхідних даних.

Приклади