Задано поле \(NxM\). Відомий час переходу з кожної клітинки поля у сусідню (по вертикалі чи горизонталі). Необхідно відповісти на \(Q\) запитів найкоротшого шляху між заданими клітинками.

Формат вхідних даних

В першому рядку два цілих числа \(N,M\) - кількість рядків та стовпців таблиці (\(1 \le N* M \le 2*10^4\))
В наступних \(N\) рядках міститься по \(M-1\) числу - час переходів між сусідніми клітинками по горизонталі в кожному з N рядків.
В наступних \(N-1\) рядках міститься по \(M\) числе - час переходів між сусідніми клітинками по вертикалі в кожному з M стовпців.
Час переходу між клітинками - ціле число від \(1\) до \(10^4\)
В наступному рядку міститься число \(Q\) - кількість запитів (\(1 \le Q \le 10^5\))
В наступних \(Q\) рядках міститься по 4 числа \(x1, y1, x2, y2\) координати клітинок між якими необхідно знайти мінімальну відстань.

Формат вихідних даних

Для кожного запиту виведіть відповідь в окремому рядку.

Приклад вхідних даних-1

2 2
2
3
6 4
2
1 1 2 2
1 2 2 1

Приклад вихідних даних-1

6
7