В небольшом городке есть множество перекрёстков, соединённых улицами. Для удобства будем считать, что перекрёстки — это узлы прямоугольной сетки $$$n \times m$$$, а дороги соединяют два перекрёстка, если эти перекрёстки являются соседними на одной горизонтальной или вертикальной линии сетки. У каждой дороги есть время, за которое её можно пройти. Параллельные участки могут проходиться за разное время по разным причинам: из-за особенностей рельефа, узости тротуара, качества покрытия, ремонта труб (который ведётся уже несколько лет кряду) и многого другого.
Мэр этого города живёт на северо-западном перекрёстке $$$(1,\ 1)$$$, а мэрия расположена на юго-восточном перекрёстке $$$(n,\ m)$$$. Согласно недавнему распоряжению сверху, чтобы лучше понимать проблемы города и горожан, каждый мэр в регионе должен перемещаться на работу и с работы пешком или на общественном транспорте, которого, как назло, в этом городке пока нет.
Мэр очень любит свою работу, поэтому каждое утро хочет на неё попасть как можно быстрее, поэтому он ходит либо на восток, либо на юг. Перепробовав разные маршруты, он нашёл наиболее быстрый, однако дорога всё ещё отнимает слишком много времени.
Вдохновившись недавними новостями, он решил одобрить инициативу местных умельцев, которым удалось прикрутить к ПАЗику на саморезы несколько небольших реактивных двигателей, которые помогут автобусу преодолевать небольшие расстояния по воздуху. Так как пока был собран лишь один образец для демонстрации мастерства умельцев, перед мэром встала задача: между какими двумя перекрёстками будет летать этот автобус.
Было предложено несколько вариантов маршрута киберавтобуса. Мэр собирается оценивать каждый вариант по целому набору критериев, один из которых — уменьшение времени путешествия между его домом и мэрией. Помогите ему это посчитать.
В первой строке записано 3 целых числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n \le 250\ 000$$$, $$$2 \le m \le 500\ 000$$$, $$$n \cdot m \le 10^6$$$, $$$1 \le q \le 10^5$$$) — размеры города и количество вариантов маршрута киберавтобуса.
В следующих $$$n$$$ строках записано по $$$m - 1$$$ целому числу $$$h_{ij}$$$ ($$$0 \lt h_{ij} \le 1000$$$) — время прохода по горизонтальной дороге от перекрёстка $$$(i,\ j)$$$ до перекрёстка $$$(i,\ j + 1)$$$ в секундах.
В следующей $$$n - 1$$$ строке записано по $$$m$$$ целых чисел $$$v_{ij}$$$ ($$$1 \le v_{ij} \le 1000$$$) — время прохода по вертикальной дороге от перекрёстка $$$(i,\ j)$$$ до перекрёстка $$$(i + 1,\ j)$$$ в секундах.
В следующих $$$q$$$ строках записано по $$$5$$$ целых чисел $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$, $$$t$$$ ($$$1 \le x_1, x_2 \le n$$$, $$$1 \le y_1,\ y_2 \le m$$$, $$$1 \le t \le 100\ 000$$$) — координаты перекрёстков, между которыми может курировать киберавтобус, и время в секундах, за которое он преодолевает это расстояние. Киберавтобус курсирует в обе стороны.
Необходимо вывести $$$q$$$ строк. В $$$i$$$-й строке должно содержаться единственное целое число — на сколько секунд сократится кратчайший путь между домом мэра и мэрией, если запустить $$$i$$$-й вариант маршрута.
3 4 41 4 72 5 83 6 914 15 16 1710 11 12 131 2 2 3 32 3 1 2 101 1 3 3 451 4 3 1 5
17 10 0 7
